844. Backspace String Compare

题目的意思大概是有两个字符串，其中的#表示退格键，让比较最后两个字符串是否相当。

很容易想到的思路就是用一个栈进行模拟这个过程，特别需要注意如果一个串是空串也是可以退格的。

但是很容易想到的另一个特性就是，前面的字符有可能被后面的退格符删去，但是如果如果从后往前进行遍历的话那么一个字符一旦保留就不会被删除，我们比较两个字符串保留下来的字符，一旦发现不相等就直接返回。

总体来讲就是双指针加逆序遍历。

其实看到这个题我直接就想到双指针加逆序遍历了。但是昨天晚上也不知道是因为困了还是什么原因，写了二十分钟写的都是错的。关键是对删除的过程理解的不够深刻，我们得到的保留的下来的字符应该有两个特征：

不是#

后面没有#来删除它
抓住这两个特征，如果有一个特征不满足就要继续删除，直到删除过程结束。
中午写了一下直接过了，果然还是白天头脑清晰一点。

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

看了一下题解，大概和题解写的差不多，但是我在上面循环删除部分写的比题解稍微好一点，题解在最后的判断写的比我好。

总结

以上是生活随笔为你收集整理的844. Backspace String Compare的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。