LeetCode 844. 比较含退格的字符串

示例 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 = "#a#c"
输出：true
解释：S 和 T 都会变成 “c”。

示例 4：
输入：S = "a#c", T = "b"
输出：false
解释：S 会变成 “c”，但 T 仍然是 “b”。
 
提示：
1 <= S.length <= 200
1 <= T.length <= 200
S 和 T 只含有小写字母以及字符 '#'。

进阶：
你可以用 O(N) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？

class Solution {
public:
    bool backspaceCompare(string S, string T) {
        process(S);
        process(T);
        int i, j;
        for(i = 0,j = 0; i < S.size() && j < T.size(); i++,j++)
        {
        	while(i < S.size() && S[i] == '#')
        		i++;//跳过#
        	while(j < T.size() && T[j] == '#')
        		j++;//跳过#
        	if((i < S.size() && j < T.size() && S[i] != T[j])
        	    || (i < S.size() && j >= T.size())
        	    || (j < T.size() && i >= S.size()))//不匹配
        		return false;
        }
        return true;
    }

    void process(string &s)//把所有n个#前面的n个字符都变成#
    {
    	int i, j;
    	for(j = 0; j < s.size(); ++j)
    	{
    		i = j-1;
    		while(j < s.size() && s[j] == '#')
    		{
    			while(i >= 0 && s[i] == '#')
    				i--;
    			if(i >= 0)
    				s[i] = '#';//变成#
    			++j;
    		}
    	}
    }
};

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        return process(s) == process(t);
    }
    
    string process(string &s) 
    {
        vector<char> v;
        for(char c : s) 
        {
            if(c == '#')
            {
                if (!v.empty()) 
                    v.pop_back();
            }
            else 
                v.push_back(c);
        }
        return string(v.begin(), v.end());
    }
};