LeetCode844-比较含退格的字符串

题目描述：
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
注意： 如果对空文本输入退格字符，文本继续为空。

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

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

示例 3：
输入：s = “a#c”, t = “b”
输出：false
解释：s 会变成 “c”，但 t 仍然是 “b”。

思路：
倒叙读取字符串，遇到#号，从#号开始继续倒叙读取，直到读取到字符为止

class Solution {
    public static boolean backspaceCompare(String s, String t) {
        String s1 = newString(s);
        String s2 = newString(t);
        return s1.equals(s2);
    }
    public static String newString(String s){
        char[] ch = s.toCharArray();
        StringBuilder builder = new StringBuilder();
        for(int i=ch.length-1;i>=0;i--){
            if(ch[i]=='#'){
                for(int j=i;j>=0;j--){
                    if(ch[j]!='#'&&ch[j]!=' '){
                        ch[j] = ' ';
                        ch[i] = ' ';
                        break;
                    }
                }
            }
        }
        for (int i = 0; i < ch.length; i++) {
            if(ch[i]!=' '&&ch[i]!='#'){
                builder.append(ch[i]);
            }
        }
        String s1 = builder.toString();
        return s1;
    }
}
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

方式二：
每次我们遍历到一个字符：

1. 如果它是退格符，那么我们将栈顶弹出；
2. 如果它是普通字符，那么我们将其压入栈中。

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