| comments | difficulty | edit_url | rating | source | tags | ||
|---|---|---|---|---|---|---|---|
true |
中等 |
1693 |
第 301 场周赛 Q3 |
|
给你两个字符串 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.length1 <= n <= 105start和target由字符'L'、'R'和'_'组成
替换操作实际上是将 L 往左移动（L 左边为 _ 时才能移动），R 往右移动（R 右边是 _ 时才能移动），但 L 无法穿过 R。所以，如果去掉 start 和 target 中的所有 _，剩下的字符应该是相同的，否则返回 false。
我们使用双指针 start 和 target：
- 如果当前字符为
L且$i\lt j$ ，那么这个L无法向右移动，返回false； - 如果当前字符为
R且$i\gt j$ ，那么这个R无法向左移动，返回false。
如果双指针均遍历到末尾，返回 true。
时间复杂度 start 或 target 的长度。
相似题目：
class Solution:
def canChange(self, start: str, target: str) -> bool:
a = [(v, i) for i, v in enumerate(start) if v != '_']
b = [(v, i) for i, v in enumerate(target) if v != '_']
if len(a) != len(b):
return False
for (c, i), (d, j) in zip(a, b):
if c != d:
return False
if c == 'L' and i < j:
return False
if c == 'R' and i > j:
return False
return Trueclass Solution {
public boolean canChange(String start, String target) {
List<int[]> a = f(start);
List<int[]> b = f(target);
if (a.size() != b.size()) {
return false;
}
for (int i = 0; i < a.size(); ++i) {
int[] x = a.get(i);
int[] y = b.get(i);
if (x[0] != y[0]) {
return false;
}
if (x[0] == 1 && x[1] < y[1]) {
return false;
}
if (x[0] == 2 && x[1] > y[1]) {
return false;
}
}
return true;
}
private List<int[]> f(String s) {
List<int[]> res = new ArrayList<>();
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == 'L') {
res.add(new int[] {1, i});
} else if (s.charAt(i) == 'R') {
res.add(new int[] {2, i});
}
}
return res;
}
}using pii = pair<int, int>;
class Solution {
public:
bool canChange(string start, string target) {
auto a = f(start);
auto b = f(target);
if (a.size() != b.size()) return false;
for (int i = 0; i < a.size(); ++i) {
auto x = a[i], y = b[i];
if (x.first != y.first) return false;
if (x.first == 1 && x.second < y.second) return false;
if (x.first == 2 && x.second > y.second) return false;
}
return true;
}
vector<pair<int, int>> f(string s) {
vector<pii> res;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == 'L')
res.push_back({1, i});
else if (s[i] == 'R')
res.push_back({2, i});
}
return res;
}
};func canChange(start string, target string) bool {
f := func(s string) [][]int {
res := [][]int{}
for i, c := range s {
if c == 'L' {
res = append(res, []int{1, i})
} else if c == 'R' {
res = append(res, []int{2, i})
}
}
return res
}
a, b := f(start), f(target)
if len(a) != len(b) {
return false
}
for i, x := range a {
y := b[i]
if x[0] != y[0] {
return false
}
if x[0] == 1 && x[1] < y[1] {
return false
}
if x[0] == 2 && x[1] > y[1] {
return false
}
}
return true
}function canChange(start: string, target: string): boolean {
if (
[...start].filter(c => c !== '_').join('') !== [...target].filter(c => c !== '_').join('')
) {
return false;
}
const n = start.length;
let i = 0;
let j = 0;
while (i < n || j < n) {
while (start[i] === '_') {
i++;
}
while (target[j] === '_') {
j++;
}
if (start[i] === 'R') {
if (i > j) {
return false;
}
}
if (start[i] === 'L') {
if (i < j) {
return false;
}
}
i++;
j++;
}
return true;
}class Solution:
def canChange(self, start: str, target: str) -> bool:
n = len(start)
i = j = 0
while 1:
while i < n and start[i] == '_':
i += 1
while j < n and target[j] == '_':
j += 1
if i >= n and j >= n:
return True
if i >= n or j >= n or start[i] != target[j]:
return False
if start[i] == 'L' and i < j:
return False
if start[i] == 'R' and i > j:
return False
i, j = i + 1, j + 1class Solution {
public boolean canChange(String start, String target) {
int n = start.length();
int i = 0, j = 0;
while (true) {
while (i < n && start.charAt(i) == '_') {
++i;
}
while (j < n && target.charAt(j) == '_') {
++j;
}
if (i == n && j == n) {
return true;
}
if (i == n || j == n || start.charAt(i) != target.charAt(j)) {
return false;
}
if (start.charAt(i) == 'L' && i < j || start.charAt(i) == 'R' && i > j) {
return false;
}
++i;
++j;
}
}
}class Solution {
public:
bool canChange(string start, string target) {
int n = start.size();
int i = 0, j = 0;
while (true) {
while (i < n && start[i] == '_') ++i;
while (j < n && target[j] == '_') ++j;
if (i == n && j == n) return true;
if (i == n || j == n || start[i] != target[j]) return false;
if (start[i] == 'L' && i < j) return false;
if (start[i] == 'R' && i > j) return false;
++i;
++j;
}
}
};func canChange(start string, target string) bool {
n := len(start)
i, j := 0, 0
for {
for i < n && start[i] == '_' {
i++
}
for j < n && target[j] == '_' {
j++
}
if i == n && j == n {
return true
}
if i == n || j == n || start[i] != target[j] {
return false
}
if start[i] == 'L' && i < j {
return false
}
if start[i] == 'R' && i > j {
return false
}
i, j = i+1, j+1
}
}function canChange(start: string, target: string): boolean {
const n = start.length;
let [i, j] = [0, 0];
while (1) {
while (i < n && start[i] === '_') {
++i;
}
while (j < n && target[j] === '_') {
++j;
}
if (i === n && j === n) {
return true;
}
if (i === n || j === n || start[i] !== target[j]) {
return false;
}
if ((start[i] === 'L' && i < j) || (start[i] === 'R' && i > j)) {
return false;
}
++i;
++j;
}
}