栈——844. 比较含退格的字符串

题目

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

示例

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

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

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

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

解题思路

1. 将S、T元素分别进栈，但元素为一个’#’，出栈一个元素；
2. 判断两个栈元素是否相等；
3. 将两个栈出栈判断是否元素相等。

   代码

   ```java import java.util.Stack;

public class Backspace_String_Compare_844 { public boolean backspaceCompare(String S, String T) { Stack sk1 = new Stack(); Stack sk2 = new Stack(); for (int i = 0;i < S.length();i++){ if (S.charAt(i) != ‘#’){ sk1.push(S.charAt(i)); }else { if (!sk1.empty()){ sk1.pop(); } } } for (int i = 0;i < T.length();i++){ if (T.charAt(i) != ‘#’){ sk2.push(T.charAt(i)); }else { if (!sk2.empty()){ sk2.pop(); } } } if (sk1.size() != sk2.size()){ return false; } else { while (!sk1.empty() && !sk2.empty()){ if (sk1.pop() != sk2.pop()){ return false; } } return true; } } }

<a name="rnEEe"></a>
## 解题思路
1. 一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉。
1. 具体地，我们定义 skip 表示当前待删除的字符的数量。每次我们遍历到一个字符：
1. 若该字符为退格符，则我们需要多删除一个普通字符，我们让skip 加 1；
1. 若该字符为普通字符：
   1. 若skip 为 0，则说明当前字符不需要删去；
   1. 若 skip 不为 0，则说明当前字符需要删去，我们让skip 减 1。
5. 这样，我们定义两个指针，分别指向两字符串的末尾。每次我们让两指针逆序地遍历两字符串，直到两字符串能够各自确定一个字符，然后将这两个字符进行比较。重复这一过程直到找到的两个字符不相等，或遍历完字符串为止。
```java
public class Backspace_String_Compare_844 {
    public boolean backspaceCompare(String S, String T) {
        int s_num = S.length()-1;
        int t_num = T.length()-1;
        int s_1 = 0;
        int t_1 = 0;
        while (true){
            while (s_num >= 0) {
                if (S.charAt(s_num) == '#') {
                    s_1++;
                } else {
                    if (s_1 > 0) {
                        s_1--;
                    } else {
                        break;
                    }
                }
                s_num--;
            }
            while (t_num >= 0){
                if (T.charAt(t_num) == '#'){
                    t_1++;
                }else {
                    if (t_1 > 0){
                        t_1--;
                    }else {
                        break;
                    }
                }
                t_num--;
            }
            if (s_num<0||t_num<0) break;
            if (S.charAt(s_num) != T.charAt(t_num)){
                return false;
            }
            s_num--;
            t_num--;
        }
        if (s_num == -1 && t_num == -1){
            return true;
        }else {
            return false;
        }
    }
}