比较含退格的字符串

发表于
本文字数： 3.6k 阅读时长 ≈ 3 分钟

LeetCode每日一题，844. Backspace String Compare

先看题目描述

0vNoy4.png

大意就是给定两个字符串 S 和 T，字符串中的 # 代表回退，问这两个字符串实际上是否相等

算法和思路

栈

思路就是用两个栈处理字符串的遍历过程，每次遍历到一个字符时：

  • 若是退格符，就将栈顶元素弹出
  • 若是普通字符，则压入栈中

最后比较两个栈中的字符是否相等即可

双指针 + 逆序遍历

这个办法是看题解才知道的

一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉

具体地，我们定义 skip 表示当前待删除的字符的数量。每次我们遍历到一个字符：

  • 若该字符为退格符，则我们需要多删除一个普通字符，将 skip + 1
  • 若该字符为普通字符：
    • 若 skip 为 0，则说明当前字符不需要删去
    • 若 skip 大于 0，则说明当前字符需要删去，将 skip - 1

这样，我们定义两个指针，分别指向两字符串的末尾。每次我们让两指针逆序地遍历两字符串，直到两字符串能够各自确定一个普通字符，然后将这两个字符进行比较。重复这一过程直到找到的两个字符不相等，或遍历完字符串为止

算法源码

栈

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
import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public boolean backspaceCompare(String S, String T) {
        int m = S.length();
        int n = T.length();
        Deque<Character> deque1 = new LinkedList<>();
        Deque<Character> deque2 = new LinkedList<>();
        for (char c: S.toCharArray()) {
            if (c == '#') {
                if (!deque1.isEmpty())
                deque1.removeLast();
            } else {
                deque1.add(c);
            }
        }
        for (char c: T.toCharArray()) {
            if (c == '#') {
                if (!deque2.isEmpty())
                    deque2.removeLast();
            } else {
                deque2.add(c);
            }
        }
        if (deque1.size() != deque2.size()) return false;
        while (deque1.size() != 0) {
            if (deque1.pop() != deque2.pop()) return false;
        }
        return true;
    }
}

下面是官方题解中用栈实现的算法代码，效率比上面这个更为优秀，我认为差距主要在于最后的比较部分，官方题解是在用栈遍历字符串的过程中重构字符串，最后比较重构后的两个字符串是否相等；而我自己实现的这个是用栈来存储实际的字符，然后遍历两个栈来进行比较，栈顶元素的弹出操作耗费了更多时间，效率要差一些

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean backspaceCompare(String S, String T) {
        return build(S).equals(build(T));
    }

    public String build(String str) {
        StringBuffer ret = new StringBuffer();
        int length = str.length();
        for (int i = 0; i < length; ++i) {
            char ch = str.charAt(i);
            if (ch != '#') {
                ret.append(ch);
            } else {
                if (ret.length() > 0) {
                    ret.deleteCharAt(ret.length() - 1);
                }
            }
        }
        return ret.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
class Solution {
    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) {
                if (S.charAt(i) != T.charAt(j)) return false;
            } else if (i >= 0 || j >= 0) {
                return false;
            }
            i--;
            j--;
        }
        return true;
    }
}