2337-移动片段得到字符串

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

给你两个字符串 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______ **R** R" 。
可以从字符串 start 得到 target ，所以返回 true 。

示例 2：

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

示例 3：

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

提示：

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

方法一：双指针

可能的移动操作有如下两种：

  • 如果一个字符 L' 左侧的相邻字符是 _‘，则将字符 L' 向左移动一位，将其左侧的 _‘ 向右移动一位；

  • 如果一个字符 R' 右侧的相邻字符是 _‘，则将字符 R' 向右移动一位，将其右侧的 _‘ 向左移动一位。

由于每次移动操作只是交换两个相邻字符，不会增加或删除字符，因此如果可以经过一系列移动操作将 start 转换成 target，则 start 和 target 满足每一种字符的数量分别相同，字符 L' 和 R’ 的相对顺序相同，且每个 L' 在 target 中的下标小于等于对应的 L’ 在 start 中的下标，以及每个 R' 在 target 中的下标大于等于对应的 R’ 在 start 中的下标。

因此，可以通过判断 start 和 target 中的所有 L' 和 R’ 是否符合替换后的规则，判断是否可以经过一系列移动操作将 start 转换成 target。

用 n 表示 start 和 target 的长度，用 i 和 j 分别表示 start 和 target 中的下标，从左到右遍历 start 和 target，跳过所有的 \_'，当 i 和 j 都小于 n 时，比较非 _‘ 的字符：

  • 如果 start}[i] \ne \textit{target}[j]，则 start 和 target 中的当前字符不匹配，返回 false；

  • 如果 start}[i] = \textit{target}[j]，则当前字符是 L' 时应有 i \ge j，当前字符是 R’ 时应有 i \le j，如果当前字符与两个下标的关系不符合该规则，返回 false。

如果 i 和 j 中有一个下标大于等于 n，则有一个字符串已经遍历到末尾，继续遍历另一个字符串中的其余字符，如果其余字符中出现非 `_‘ 的字符，则该字符不能与任意字符匹配，返回 false。

如果 start 和 target 遍历结束之后没有出现不符合移动操作的情况，则可以经过一系列移动操作将 start 转换成 target，返回 true。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def canChange(self, start: str, target: str) -> bool:
        n = len(start)
        i = j = 0
        while i < n and j < n:
            while i < n and start[i] == '_':
                i += 1
            while j < n and target[j] == '_':
                j += 1
            if i < n and j < n:
                if start[i] != target[j]:
                    return False
                c = start[i]
                if c == 'L' and i < j or c == 'R' and i > j:
                    return False
                i += 1
                j += 1
        while i < n:
            if start[i] != '_':
                return False
            i += 1
        while j < n:
            if target[j] != '_':
                return False
            j += 1
        return True
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public boolean canChange(String start, String target) {
        int n = start.length();
        int i = 0, j = 0;
        while (i < n && j < n) {
            while (i < n && start.charAt(i) == '_') {
                i++;
            }
            while (j < n && target.charAt(j) == '_') {
                j++;
            }
            if (i < n && j < n) {
                if (start.charAt(i) != target.charAt(j)) {
                    return false;
                }
                char c = start.charAt(i);
                if ((c == 'L' && i < j) || (c == 'R' && i > j)) {
                    return false;
                }
                i++;
                j++;
            }
        }
        while (i < n) {
            if (start.charAt(i) != '_') {
                return false;
            }
            i++;
        }
        while (j < n) {
            if (target.charAt(j) != '_') {
                return false;
            }
            j++;
        }
        return true;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Solution {
    public bool CanChange(string start, string target) {
        int n = start.Length;
        int i = 0, j = 0;
        while (i < n && j < n) {
            while (i < n && start[i] == '_') {
                i++;
            }
            while (j < n && target[j] == '_') {
                j++;
            }
            if (i < n && j < n) {
                if (start[i] != target[j]) {
                    return false;
                }
                char c = start[i];
                if ((c == 'L' && i < j) || (c == 'R' && i > j)) {
                    return false;
                }
                i++;
                j++;
            }
        }
        while (i < n) {
            if (start[i] != '_') {
                return false;
            }
            i++;
        }
        while (j < n) {
            if (target[j] != '_') {
                return false;
            }
            j++;
        }
        return true;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    bool canChange(string start, string target) {
        int n = start.length();
        int i = 0, j = 0;
        while (i < n && j < n) {
            while (i < n && start[i] == '_') {
                i++;
            }
            while (j < n && target[j] == '_') {
                j++;
            }
            if (i < n && j < n) {
                if (start[i] != target[j]) {
                    return false;
                }
                char c = start[i];
                if ((c == 'L' && i < j) || (c == 'R' && i > j)) {
                    return false;
                }
                i++;
                j++;
            }
        }
        while (i < n) {
            if (start[i] != '_') {
                return false;
            }
            i++;
        }
        while (j < n) {
            if (target[j] != '_') {
                return false;
            }
            j++;
        }
        return true;
    }
};
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
bool canChange(char * start, char * target) {
    int n = strlen(start);
    int i = 0, j = 0;
    while (i < n && j < n) {
        while (i < n && start[i] == '_') {
            i++;
        }
        while (j < n && target[j] == '_') {
            j++;
        }
        if (i < n && j < n) {
            if (start[i] != target[j]) {
                return false;
            }
            char c = start[i];
            if ((c == 'L' && i < j) || (c == 'R' && i > j)) {
                return false;
            }
            i++;
            j++;
        }
    }
    while (i < n) {
        if (start[i] != '_') {
            return false;
        }
        i++;
    }
    while (j < n) {
        if (target[j] != '_') {
            return false;
        }
        j++;
    }
    return true;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
var canChange = function(start, target) {
    const n = start.length;
    let i = 0, j = 0;
    while (i < n && j < n) {
        while (i < n && start[i] === '_') {
            i++;
        }
        while (j < n && target[j] === '_') {
            j++;
        }
        if (i < n && j < n) {
            if (start[i] !== target[j]) {
                return false;
            }
            const c = start[i];
            if ((c === 'L' && i < j) || (c === 'R' && i > j)) {
                return false;
            }
            i++;
            j++;
        }
    }
    while (i < n) {
        if (start[i] !== '_') {
            return false;
        }
        i++;
    }
    while (j < n) {
        if (target[j] !== '_') {
            return false;
        }
        j++;
    }
    return true;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func canChange(start string, target string) bool {
    i, j, n := 0, 0, len(start)
    for i < n && j < n {
        for i < n && start[i] == '_' {
            i++
        }
        for j < n && target[j] == '_' {
            j++
        }
        if i < n && j < n {
            if start[i] != target[j] {
                return false
            }
            c := start[i]
            if c == 'L' && i < j || c == 'R' && i > j {
                return false
            }
            i++
            j++
        }
    }
    for i < n {
        if start[i] != '_' {
            return false
        }
        i++
    }
    for j < n {
        if target[j] != '_' {
            return false
        }
        j++
    }
    return true
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是字符串 start 和 target 的长度。需要遍历两个字符串各一次。

  • 空间复杂度：O(1)。只需要使用常量的额外空间。

 Comments
On this page
2337-移动片段得到字符串