每日 LeetCode] 844. Backspace String Compare

Description:

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

Example 1:

Input: S = "ab#c", T = "ad#c"
Output: true 
Explanation: Both S and T become "ac".
​

Example 2:

Input: S = "ab##", T = "c#d#"
Output: true 
Explanation: Both S and T become "".
​

Example 3:

Input: S = "a##c", T = "#a#c"
Output: true 
Explanation: Both S and T become "c".
​

Example 4:

Input: S = "a#c", T = "b"
Output: false 
Explanation: S becomes "c" while T becomes "b".
​

Note:

1. 1 <= S.length <= 200
2. 1 <= T.length <= 200
3. S and T only contain lowercase letters and '#' characters.

本题要求去除两个字符串中的 #，# 的功能是可以删除 # 之前的字符，判断两个消去 # 的字符串是否相同。

思路一：借助栈，扫描字符串，依次进栈，遇到 # 就降栈中已有的元素弹出，最后比较两个栈是否相同。

思路二：很高大上，时间空间均超过了 100%， 暂时还没有理解，先记下来吧有，有理解的朋友还请多多指教。

C++ 代码（思路一）

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        stack<char> a;
        stack<char> b;
        for (auto s : S){
            if (s == '#'){
                if (a.size() !=0 )
                    a.pop();
            }
            else
                a.push(s);
                //continue;
        }
        for (auto t : T){
            if (t == '#'){
                if (b.size() != 0)
                    b.pop();
            }   
            else
                b.push(t);
        }
        return a == b;
    }
};
​

运行时间：12ms

运行内存：8.6M

C++ 代码（思路二）

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        int i = S.size() - 1, j = T.size() - 1, countA = 0, countB = 0;
        while (i >= 0 || j >= 0) {
            while (i >= 0 && (S[i] == '#' || countA > 0)) 
                S[i--] == '#' ? countA++ : countA--;
            while (j >= 0 && (T[j] == '#' || countB > 0)) 
                T[j--] == '#' ? countB++ : countB--;
            if (i < 0 || j < 0) 
                return i == j;
            if (S[i--] != T[j--]) 
                return false;
        }
        return i == j;
    }
};
​

运行时间：4ms

运行内存：8.4M