2337. 移动片段得到字符串

2337. 移动片段得到字符串

题目描述：

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

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

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

数据范围：

$1\le n \le 10^5$

题解：

因为L只能向左移动，所以相同的L， $start_i \ge target_j$ ；同理可得相同的R， $start_i \le target_j$ 。这样才能够通过移动得到 $target$ 。可以直接忽略_，只看相同字母，如果字母不相同直接返回false，相同的时候按照上述规则判断。

代码：

auto init = []()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
class Solution {
public:
    bool canChange(string start, string target) {
        int i = 0, j = 0;
        int n = target.size();
        while(i < n || j < n)
        {
            while(i < n && start[i] == '_') ++i;
            while(j < n && target[j] == '_') ++j;
            if(i >= n && j >= n) return true;
            if(start[i] != target[j]) return false;
            if(start[i] == 'L' && i < j || start[i] == 'R' && i > j) return false;
            ++i;
            ++j;
        }
        return true;
    }
};