LeetCode844-比较含退格的字符串

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/backspace-string-compare/

中文链接：https://leetcode-cn.com/problems/backspace-string-compare/

题目详述

给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。

示例 1：

1
2
3
输入：S = "ab#c", T = "ad#c"
输出：true
解释：S 和 T 都会变成 “ac”。

示例 2：

1
2
3
输入：S = "ab##", T = "c#d#"
输出：true
解释：S 和 T 都会变成 “”。

示例 3：

1
2
3
输入：S = "a##c", T = "#a#c"
输出：true
解释：S 和 T 都会变成 “c”。

示例 4：

1
2
3
输入：S = "a#c", T = "b"
输出：false
解释：S 会变成 “c”，但 T 仍然是 “b”。

提示：

  1. 1 <= S.length <= 200
  2. 1 <= T.length <= 200
  3. S 和 T 只含有小写字母以及字符 '#'。

题目详解

运用栈即可。

  • 两个栈对应两个字符串。
  • 遍历字符串的每个字符。
  • 如果不是 #，入栈。
  • 如果是 #，如果栈不为空，弹出栈顶元素。
  • 当遍历完两个字符串序列后，两个栈相等说明符合要求。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class LeetCode_00844 {

    public boolean backspaceCompare(String S, String T) {
        Stack<Character> s1 = new Stack<>();
        Stack<Character> s2 = new Stack<>();
        for (char c : S.toCharArray()) {
            if (c != '#') {
                s1.push(c);
            } else if (!s1.isEmpty()) {
                s1.pop();
            }
        }
        for (char c : T.toCharArray()) {
            if (c != '#') {
                s2.push(c);
            } else if (!s2.isEmpty()) {
                s2.pop();
            }
        }
        return s1.equals(s2);
    }
}

当然，我们也可以运用指针来手动模拟这个过程。为了方便，可以从后往前遍历字符串。

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
44
45
46
public class LeetCode_00844 {

    public boolean backspaceCompare(String S, String T) {
        int i = S.length() - 1;
        int j = T.length() - 1;
        int skipS = 0;
        int skipT = 0;
        while (i >= 0 || j >= 0) {
            // 找到 S 下一个可能比较的字符
            while (i >= 0) {
                if (S.charAt(i) == '#') {
                    ++skipS;
                    --i;
                } else if (skipS > 0) {
                    --skipS;
                    --i;
                } else {
                    break;
                }
            }
            // 找到 T 下一个可能比较的字符
            while (j >= 0) {
                if (T.charAt(j) == '#') {
                    ++skipT;
                    --j;
                } else if (skipT > 0) {
                    --skipT;
                    --j;
                } else {
                    break;
                }
            }
            // 两个字符不相等
            if (i >= 0 && j >= 0 && S.charAt(i) != T.charAt(j)) {
                return false;
            }
            // 有字符和无字符
            if ((i >= 0) != (j >= 0)) {
                return false;
            }
            --i;
            --j;
        }
        return true;
    }
}