2337. Move Pieces to Obtain a String

Problem

You are given two strings start and target, both of length n. Each string consists only of the characters 'L', 'R', and '_' where:

• The characters 'L' and 'R' represent pieces, where a piece 'L' can move to the left only if there is a blank space directly to its left, and a piece 'R' can move to the right only if there is a blank space directly to its right.
• The character '_' represents a blank space that can be occupied by any of the 'L' or 'R' pieces.

Return true if it is possible to obtain the string target by moving the pieces of the string start any number of times. Otherwise, return false.

https://leetcode.com/problems/move-pieces-to-obtain-a-string/

Example 1:

Input: start = "_L__R__R_", target = "L______RR"
Output: true
Explanation: We can obtain the string target from start by doing the following moves:

• Move the first piece one step to the left, start becomes equal to "L___R__R_".
• Move the last piece one step to the right, start becomes equal to "L___R___R".
• Move the second piece three steps to the right, start becomes equal to "L______RR".

Since it is possible to get the string target from start, we return true.

Example 2:

Input: start = "R_L_", target = "__LR"
Output: false
Explanation: The 'R' piece in the string start can move one step to the right to obtain "_RL_".
After that, no pieces can move anymore, so it is impossible to obtain the string target from start.

Example 3:

Input: start = "_R", target = "R_"
Output: false
Explanation: The piece in the string start can move only to the right, so it is impossible to obtain the string target from start.

Constraints:

• n == start.length == target.length
• 1 <= n <= 10⁵
• start and target consist of the characters 'L', 'R', and '_'.

Test Cases

1
2

class Solution:
    def canChange(self, start: str, target: str) -> bool:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

import pytest

from solution import Solution
from solution2 import Solution as Solution2


@pytest.mark.parametrize('start, target, expected', [
    ("_L__R__R_", "L______RR", True),
    ("R_L_", "__LR", False),
    ("_R", "R_", False),

    ("RL_", "_RL", False),
])
class Test:
    def test_solution(self, start, target, expected):
        sol = Solution()
        assert sol.canChange(start, target) == expected

    def test_solution2(self, start, target, expected):
        sol = Solution2()
        assert sol.canChange(start, target) == expected

Thoughts

首先 start 和 target 中 L 和 R 的排列顺序必须完全一致，否则怎么移动都没用。

从 start 和 target 最左开始，分别取下一个非空白的 piece（设下标分别为 i、j），如果两个 piece 不一样（一个是 L 另一个是 R）则一定不行。

如果两个 pieces 都是 L，则 i < j 时不行。反之，如果两个 pieces 都是 R，则 i > j 时不行。

因为有可能一个字符串先扫描完了，需要检查另一个字符串剩余的部分是否都是空白，如果还有非空白的 piece 也不行。

O(n) 时间，O(1) 空间。

还有一个办法是同步扫描 start 和 target（下标始终一致）。用变量记录 start 里有几个 R 在右移中，或者在 target 里见到了几个 L 等着 start 提供（需求量）（两种情况不能同时出现，可以用一个变量的正数和负数记录）。根据 start 和 target 当前的 piece 判断是否可行。

1. start 当前 piece 是 R：如果在等着 L 则失败；否则 R 数量加一。
2. target 当前 piece 是 R：如果 R 数量为 0 则失败；否则 R 数量减一。
3. target 当前 piece 是 L：如果已经有 R 了则失败；否则 L 的需求量加一。
4. start 当前 piece 是 L：如果 L 的需求量为 0 则失败；否则 L 需求量减一。

注意边界条件要求 2 必须在 1 之后判定，4 必须在 3 之后判定。

最后如过还有遗留的 L 的需求量或 R 的数量，则失败。

也是 O(n) 时间，O(1) 空间。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def canChange(self, start: str, target: str) -> bool:
        n = len(start)
        i = j = 0
        while i < n and j < n:
            if start[i] == '_':
                i += 1
            elif target[j] == '_':
                j += 1
            elif start[i] != target[j]:
                return False
            elif start[i] == 'L':
                if i < j:
                    return False
                i += 1
                j += 1
            else: # start[i] == 'R'
                if i > j:
                    return False
                i += 1
                j += 1

        return all(start[k] == '_' for k in range(i, n)) and all(target[k] == '_' for k in range(j, n))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def canChange(self, start: str, target: str) -> bool:
        bal = 0 # bal < 0: there are some `L`s requested by `target`; bal > 0: `start` has some `R`s to move right.
        for s, t in zip(start, target):
            if s == 'R':
                if bal < 0: # `L` is already requested, but get an `R` in `start`.
                    return False
                bal += 1
            if t == 'R':
                if bal <= 0: # `start` doesn't have `R` to match it.
                    return False
                bal -= 1

            if t == 'L':
                if bal > 0: # `start` already had some `R`s, but `target` is `L`.
                    return False
                bal -= 1
            if s == 'L':
                if bal >= 0: # `L` is not requested, but get one.
                    return False
                bal += 1

        return bal == 0

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章