2337. 移动片段得到字符串

题目描述

给你两个字符串 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.length
1 <= n <= 10⁵
start 和 target 由字符 'L'、'R' 和 '_' 组成

解法一：双指针

 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


func canChange(start string, target string) bool {
    i, j, n := 0, 0, len(start)
    for {
        for i < n && start[i] == '_' {
            i++
        }
        for j < n && target[j] == '_' {
            j++
        }
        if i == n || j == n {
            break
        }
        if start[i] != target[j] {
            return false
        }
        if start[i] == 'L' && j > i || start[i] == 'R' && j < i {
            return false
        }
        i++
        j++
    }
    if i == n || j == n {
        for i < n && start[i] == '_' {
            i++
        }
        for j < n && target[j] == '_' {
            j++
        }
        if i != n || j != n {
            return false
        }
    }
    return true
}