移动片段得到字符串【LC2337】
给你两个字符串 start 和 target ，长度均为 n 。每个字符串 仅 由字符 'L'、'R' 和 '_' 组成，其中：
字符 'L' 和 'R' 表示片段，其中片段 'L' 只有在其左侧直接存在一个 空位 时才能向 左 移动，而片段 'R' 只有在其右侧直接存在一个 空位 时才能向 右 移动。
字符 '_' 表示可以被 任意 'L' 或 'R' 片段占据的空位。
如果在移动字符串 start 中的片段任意次之后可以得到字符串 target ，返回 true ；否则，返回 false 。
双指针
思路
如果start进行移动可以的带target，那么将"_“替换为”"后，两个字符串一定相等。由于’L’只能左移，‘R’只能右移，那么可以使用双指针i、j定位字符串start和target中不是’_'的位置
实现
class Solution { public boolean canChange(String start, String target) { if (!start.replaceAll("_", "").equals(target.replaceAll("_", ""))) return false; for (int i = 0, j = 0; i < start.length(); i++) { if (start.charAt(i) == '_') continue; while (target.charAt(j) == '_') j++; if (i != j && (start.charAt(i) == 'L') == (i < j)) return false; ++j; } return true; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/move-pieces-to-obtain-a-string/solutions/1658923/nao-jin-ji-zhuan-wan-pythonjavacgo-by-en-9sqt/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度
时间复杂度：O ( n )
空间复杂度：O ( n )
计分
- 思路
start中的’L’和’R’记为1分，target中’L’和’R’记为-1分- 由于L和R不互穿透，即L不能移动至R的右边，R不能移动至L的左边，当出现以下情况时返回
false
实现
class Solution { public boolean canChange(String start, String target) { int l = 0, r = 0; int n = start.length(); for (int i = 0; i < n; i++){ if (start.charAt(i) == 'L'){ if (r > 0) return false; l++; }else if (start.charAt(i) == 'R'){ if (l < 0) return false; r++; } if (target.charAt(i) == 'L'){ if (r > 0) return false; l--; }else if (target.charAt(i) == 'R'){ if (l < 0) return false; r--; } if (l > 0 || r < 0) return false; } return l == 0 && r == 0; } }
复杂度
时间复杂度：O ( n )
空间复杂度：O ( n )
