LeetCode844. 比较含退格的字符串

844. 比较含退格的字符串

一、题目

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

示例 1：
输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。
1
2
3
4

示例 2：
输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 ""。
1
2
3
4

示例 3：`
输入：s = "a#c", t = "b"`
输出：false`
解释：s 会变成 "c"，但 t 仍然是 "b"。
1
2
3
4

提示：

• 1 <= s.length, t.length <= 200
• s 和 t 只含有小写字母以及字符 ‘#’

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/backspace-string-compare
著作权归领扣网络所有。

二、思路及代码

方法一：暴力求解

（1）当s[i]不等于#的时候，不断赋值；当等于的时候，抛弃结尾。

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        string s1, t1;
        int k = 0;
        //当s[i]不等于#的时候，不断赋值；当等于的时候，抛弃结尾
        for(int i = 0; i < s.length(); i++){
            if(s[i] != '#'){
                s1.push_back(s[i]);
            }else if(!s1.empty()){
                s1.pop_back();
            }
        } 
        for(int i = 0; i < t.length(); i++){
            if(t[i] != '#'){
                t1.push_back(t[i]);
            }else if(!t1.empty()){
                t1.pop_back();
            }
        }   
        return (s1==t1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

方法二：双指针法（一个我看到的很厉害的题解）

demigodliu的题解

由于 # 号只会消除左边的一个字符，所以对右边的字符无影响，所以我们选择从后往前遍历 S，T 字符串。

思路解析：

准备两个指针 i, j 分别指向 S，T 的末位字符，再准备两个变量 skipS，skipT来分别存放 S，T 字符串中的 # 数量。
从后往前遍历 S，所遇情况有三，如下所示：
2.1 若当前字符是 #，则 skipS 自增 1；
2.2 若当前字符不是 #，且 skipS 不为 0，则 skipS 自减 1；
2.3 若当前字符不是 #，且 skipS 为 0，则代表当前字符不会被消除，我们可以用来和 T 中的当前字符作比较。
若对比过程出现 S, T 当前字符不匹配，则遍历结束，返回 false，若 S，T 都遍历结束，且都能一一匹配，则返回 true。

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        int i = S.length() - 1, j = T.length() - 1;
        int skipS = 0, skipT = 0;
		//如果两个数组中指针所指向的值都是最终会存在的，那么两个指针均一次一次移动
        //如果#数量大于0了，那么移动到#被抵消为止的下一位；然后第二个数组再这么做，两者比较
        //注意判断条件，因为这个和后面的i >= 0 || j >= 0相呼应
        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (S[i] == '#') {
                    skipS++, i--;
                } else if (skipS > 0) {
                    skipS--, i--;
                } else {
                    break;
                }
            }
            while (j >= 0) {
                if (T[j] == '#') {
                    skipT++, j--;
                } else if (skipT > 0) {
                    skipT--, j--;
                } else {
                    break;
                }
            }
            if (i >= 0 && j >= 0) {
                if (S[i] != T[j]) {
                    return false;
                }
            } else {//i<0 || j<0(其中一个必然小于0才会执行下一条语句)
  //如果其中一个大于等于0，那么另一个必然小于0，说明它们异号了，也说明这两个最终数组不可能相等了
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            i--, j--;
        }
        return true;
    }
};
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

作者：demigodliu
链接：https://leetcode.cn/problems/backspace-string-compare/solution/shuang-zhi-zhen-bi-jiao-han-tui-ge-de-zi-8fn8/
来源：力扣（LeetCode）
著作权归作者所有。