Leetcode 2023-08-21 题目分享

Leetcode

2337. 移动片段得到字符串 - 力扣（LeetCode）

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

字符 'L' 和 'R' 表示片段，其中片段 'L' 只有在其左侧直接存在一个空位时才能向左移动，而片段 'R' 只有在其右侧直接存在一个空位时才能向右移动。

字符 '_' 表示可以被任意 'L' 或 'R' 片段占据的空位。

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

示例 1：
1
2
3
4
5
6
7
输入：start = "_L__R__R_", target = "L______RR"
输出：true
解释：可以从字符串 start 获得 target ，需要进行下面的移动：
- 将第一个片段向左移动一步，字符串现在变为 "L___R__R_" 。
- 将最后一个片段向右移动一步，字符串现在变为 "L___R___R" 。
- 将第二个片段向右移动散步，字符串现在变为 "L______RR" 。
可以从字符串 start 得到 target ，所以返回 true 。
示例 2：
1
2
3
4
输入：start = "R_L_", target = "__LR"
输出：false
解释：字符串 start 中的 'R' 片段可以向右移动一步得到 "_RL_" 。
但是，在这一步之后，不存在可以移动的片段，所以无法从字符串 start 得到 target 。
示例 3：
1
2
3
输入：start = "_R", target = "R_"
输出：false
解释：字符串 start 中的片段只能向右移动，所以无法从字符串 start 得到 target 。
提示：

n == start.length == target.length

1 <= n <= 10^5

start 和 target 由字符 'L'、'R' 和 '_' 组成

思路

明确L和R不能相互穿过，所以去除’__’后，两个字符串肯定是相等的。
从右到左遍历，依次取出两个字符串start 和 target的第一个有效字符进行判断。
- 不等: false
- 等于R且i > j: false
- 等于L且i < j: false
最后跳出循环后，可能还有字符串存在有效字符，此时返回false,否则true。

代码

class Solution {
public:
    bool canChange(string start, string target) {
        int n = start.size(), i = n-1, j = n-1;
        for (;i >= 0, j >= 0;i--, j--){
            while (i >= 0 && start[i] == '_') i--;
            while (j >= 0 && target[j] == '_') j--;
            if (i < 0 || j < 0) break;
            if (start[i] != target[j]) return false;
            if (start[i]=='R' && i > j) return false;
            if (start[i]=='L' && i < j) return false;
        }
        for (;i >= 0;i--) if (start[i] != '_') return false;
        for (;j >= 0;j--) if (target[j] != '_') return false;
        return 1;
    }
};

复杂度分析

时间复杂度: O(1) 。
空间复杂度: O(n) 。