在LR字符串中交换相邻字符

Posted on In Views: Waline: Views: Symbols count in article: 826 Reading time ≈ 1 mins.

题解方法

  • 双指针

双指针

  • 两种交换可视为 L 字符可一直左移，直到碰到 R 字符；R 字符可一直右移，直到碰到 L 字符
  • 问题转化为两字符的相对位置是否一致

核心代码

两指针

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
40
41
42
43
// 双指针同时遍历
while (i < n && j < n) {
    // 找到下一个不为 X 的字符
    while (i < n && start.charAt(i) == CHAR_X) {
        i++;
    }
    while (j < n && end.charAt(j) == CHAR_X) {
        j++;
    }

    if (i < n && j < n) {
        // 如果两个字符不相等，说明顺序不一致
        if (start.charAt(i) != end.charAt(j)) {
            return false;
        }

        char ch = start.charAt(i);
        // 字符为 L，i 应小于 j
        if (ch == CHAR_L && j > i) {
            return false;
        }
        // 字符为 R，i 应大于 j
        if (ch == CHAR_R && j < i) {
            return false;
        }

        i++;
        j++;
    }
}
// 如果有剩余的非 X 字符，说明顺序不一致
while (i < n) {
    if (start.charAt(i) != CHAR_X) {
        return false;
    }
    i++;
}
while (j < n) {
    if (end.charAt(j) != CHAR_X) {
        return false;
    }
    j++;
}

题目来源

777. 在LR字符串中交换相邻字符 - 力扣（LeetCode）