LeetCode844 backspaceCompare


LeetCode地址

模拟栈思想

我们可以使用栈的思想来模拟这个过程。从左到右遍历字符串，当遇到字符时，将其压入栈中，当遇到 ‘#’ 时，弹出栈顶字符，表示退格。最后，比较两个字符串栈中的内容是否相等。

代码展示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean backspaceCompare(String s, String t) {
    return buildString(s).equals(buildString(t));
}

private String buildString(String str) {
    StringBuilder sb = new StringBuilder();
    for (char c : str.toCharArray()) {
        if (c != '#') {
            sb.append(c);
        } else if (sb.length() > 0) {
            sb.deleteCharAt(sb.length() - 1);
        }
    }
    return sb.toString();
}

双指针方法

除了使用栈的方法，我们还可以采用双指针的方式，从字符串末尾开始逐个字符比较，遇到 ‘#’ 时跳过下一个非 ‘#’ 字符，继续比较。

代码展示

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
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) {
        while (i >= 0) {
            if (s.charAt(i) == '#') {
                skipS++;
                i--;
            } else if (skipS > 0) {
                skipS--;
                i--;
            } else {
                break;
            }
        }
        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;
}