2337.移动片段得到字符串：双指针

【LetMeFly】2337.移动片段得到字符串：双指针

力扣题目链接：https://leetcode.cn/problems/move-pieces-to-obtain-a-string/

给你两个字符串 start 和 target ，长度均为 n 。每个字符串 仅 由字符 'L'、'R' 和 '_' 组成，其中：

• 字符 'L' 和 'R' 表示片段，其中片段 'L' 只有在其左侧直接存在一个 空位 时才能向 左 移动，而片段 'R' 只有在其右侧直接存在一个 空位 时才能向 右 移动。
• 字符 '_' 表示可以被 任意 'L' 或 'R' 片段占据的空位。

如果在移动字符串 start 中的片段任意次之后可以得到字符串 target ，返回 true ；否则，返回 false 。

 

示例 1：

输入：start = "_L__R__R_", target = "L______RR"
输出：true
解释：可以从字符串 start 获得 target ，需要进行下面的移动：
- 将第一个片段向左移动一步，字符串现在变为 "L___R__R_" 。
- 将最后一个片段向右移动一步，字符串现在变为 "L___R___R" 。
- 将第二个片段向右移动散步，字符串现在变为 "L______RR" 。
可以从字符串 start 得到 target ，所以返回 true 。

示例 2：

输入：start = "R_L_", target = "__LR"
输出：false
解释：字符串 start 中的 'R' 片段可以向右移动一步得到 "_RL_" 。
但是，在这一步之后，不存在可以移动的片段，所以无法从字符串 start 得到 target 。

示例 3：

输入：start = "_R", target = "R_"
输出：false
解释：字符串 start 中的片段只能向右移动，所以无法从字符串 start 得到 target 。

 

提示：

• n == start.length == target.length
• 1 <= n <= 105
• start 和 target 由字符 'L'、'R' 和 '_' 组成

方法一：双指针

满足以下条件时，返回True：

1. 去掉_后，字符串相同（LR的相对位置及数量相同）
2. start中的L的位置不早于对应的*target中的L
3. start中的R的位置不晚于对应的*target中的R

细节描述（具体实现）：

可以使用两个指针分别指向两个字符串中遍历到的位置。

每次指针都指到L或R（或字符串末尾）为止：

• 若二者不同，则说明去掉_后剩余的LR不对应
• 否则：
  • 若指针指向的字符为L：若第一个指针小于第二个指针，返回false
  • 否则（指向的字符为R）：若第一个指针大于第二个指针，返回false

结束上述循环后，为防止一个字符串指完而另一个字符串还未遍历完的情况，遍历未遍历完的字符串，遇到非下划线就返回false。

若未返回过false，则返回true。

• 时间复杂度$O(len(target))$
• 空间复杂度$O(1)$

AC代码

C++

class Solution {
public:
    bool canChange(string& a, string& b) {
        int n = a.size();
        int ia = -1, ib = -1;
        while (ia + 1 < n && ib + 1 < n) {
            while (++ia < n && a[ia] == '_');
            while (++ib < n && b[ib] == '_');
            if (a[ia] != b[ib]) {
                return false;
            }
            if (a[ia] == 'L') {
                if (ia < ib) {
                    return false;
                }
            }
            else {  // R
                if (ia > ib) {
                    return false;
                }
            }
        }
        while (ia + 1 < n) {
            if (a[++ia] != '_') {
                return false;
            }
        }
        while (ib + 1 < n) {
            if (b[++ib] != '_') {
                return false;
            }
        }
        return true;
    }
};

Python

class Solution:
    def canChange(self, a: str, b: str) -> bool:
        n = len(a)
        ia, ib = 0, 0
        while ia < n and ib < n:
            while ia < n and a[ia] == '_':
                ia += 1
            while ib < n and b[ib] == '_':
                ib += 1
            if ia >= n or ib >= n:
                break
            if a[ia] != b[ib]:
                return False
            if a[ia] == 'L':  # L
                if ia < ib:
                    return False
            else:  # R
                if ia > ib:
                    return False
            ia, ib = ia + 1, ib + 1
        while ia < n:
            if a[ia] != '_':
                return False
            ia += 1
        while ib < n:
            if b[ib] != '_':
                return False
            ib += 1
        return True

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/132421605