当前位置 博文首页 > sodaxyh的博客：【Leetcode-算法】844. 比较含退格的字符串（C++
给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
思路：
? ? ? ? 两个思路。
? ? ? ? 第一种思路是用栈来保存退格处理后的字符串（#就弹出，否则压入）。然后比较两个栈中处理后的字符串是否一致。但这种算法会占用额外的空间，会提高空间复杂度。于是有了第二种思路。
? ? ? ? 第二种思路是用双指针。因为退格符只影响它前面的字符，不会影响后面的，所以可以从后往前遍历字符串，遇到退格符就skip字符即可，这种做法只需要常数级别的额外空间。
AC代码：（思路二）
class Solution {
public:
bool backspaceCompare(string S, string T) {
int p=S.length()-1,q=T.length()-1;
int cntS=0,cntT=0;
while(p>=0 || q>=0){
while(p>=0){
if(S[p]=='#') cntS++,p--;
else if(cntS>0) cntS--,p--;
else break;
}
while(q>=0){
if(T[q]=='#') cntT++,q--;
else if(cntT>0) cntT--,q--;
else break;
}
if(p>=0 && q>=0){
if(S[p]!=T[q]) return false;
}else if(p>=0 || q>=0){
return false;
}
p--,q--;
}
return true;
}
};?
cs