比较字符串与退格题目链接：https://leetcode-cn.com/problems/backspace-string-compare给定两个字符串S和T，当它们被输入到文本编辑器的空格后，判断是否两个相等并返回结果。#代表退格字符。注意：如果为空文本输入退格字符，文本将继续为空。示例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”。思路本文将给出空间复杂度的栈模拟方法和空间复杂度的双指针方法。常用的方法（使用栈的思路）一看就是使用栈的节奏。这种匹配（消除）问题也是stack擅长的地方。跟题的同学应该都知道，在栈和队列中：匹配问题是栈的强项，我已经说过一次用栈来做类似的事情。所以这道题确实可以用stack的思路，但是没必要用stack，因为在比较的最后还要比较stack里面的元素，有点麻烦。这里直接把字符串string当栈，在最后添加和弹出，string有对应的接口。在最后的比较中，只需要比较两个字符串，比比较栈中的元素更方便。代码如下：classSolution{public:boolbackspaceCompare(stringS,stringT){strings;//将stringt用作栈;//将stringt用作栈for(inti=0;i=0){//从后往前，剔除S的#if(S[i]=='#')sSkipNum++;else{if(sSkipNum>0)sSkipNum--;elsebreak;}i--;}while(j>=0){//从后往前，剔除T的#if(T[j]=='#')tSkipNum++;else{if(tSkipNum>0)tSkipNum--;elsebreak;}j--;}//去掉#的后半部分，然后比较S[i]!=T[j]if(i<0||j<0)break;//S或T已经遍历结束if(S[i]!=T[j])returnfalse;i--;j--;}//表示S和T同时遍历如果（我==-1&&j==-1）返回真；返回假；}}；时间复杂度：空间复杂度：其他语言版本Java://普通方法（使用栈思想）classSolution{publicbooleanbackspaceCompare(Strings,Stringt){StringBuilderssb=newStringBuilder();//模拟栈StringBuildertsb=newStringBuilder();//模拟栈//分别处理两个Stringfor(charc:s.toCharArray()){if(c!='#'){ssb.append(c);//模拟入栈}elseif(ssb.length()>0){//只有栈不为空才能出栈ssb.deleteCharAt(ssb.length()-1);//模拟出栈}}for(charc:t.toCharArray()){if(c!='#'){tsb.append(c);//模拟堆叠}elseif(tsb.length()>0){//堆叠只能是如果堆栈不为空则弹出tsb.deleteCharAt(tsb.length()-1);//模拟弹出栈}}returnssb.toString().equals(tsb.toString());}}pythonclassSolution:defget_string(self,s:str)->str:bz=[]foriinrange(len(s)):c=s[i]ifc!='#':bz.append(c)#模拟入栈eliflen(bz)>0:#只有入栈才能出栈不为空bz.pop()#模拟栈returnstr(bz)defbackspaceCompare(self,s:str,t:str)->bool:returnself.get_string(s)==self.get_string(t)passGofuncgetString(sstring)string{bz:=[]rune{}for_,c:=ranges{ifc!='#'{bz=append(bz,c);//模拟堆叠}elseiflen(bz)>0{//堆叠只能不为空则出栈bz=bz[:len(bz)-1]//模拟出栈}}returnstring(bz)}funcbackspaceCompare(sstring,tstring)bool{returngetString(s)==getString(t)}JavaScript//双栈varbackspaceCompare=function(s,t){constarrS=[],arrT=[];//数组作为栈for(letcharofs){char==='#'?arrS.pop():arrS.push(char);}for(letcharoft){char==='#'?arrT.pop():arrT.push(char);}returnarrS.join('')===arrT.join('');//比较两个字符串相等l};//双栈精简varbackspaceCompare=function(s,t){constgetString=s=>{letarrS=[];for(letcharofs){char==='#'?arrS.pop():arrS.推（字符）；}returnarrS。加入（''）;}返回getString(s)===getString(t);};//双指针varbackspaceCompare=function(s,t){letsSkipNum=0;//#记录数slettSkipNum=0;//#记录数tleti=s.length-1,j=t.length-1;while(true){while(i>=0){//从后往前，消去s#if(s[i]==='#')sSkipNum++;else{if(sSkipNum>0)sSkipNum--;elsebreak;}i--;}while(j>=0){//从后往前，消除t#if(t[j]==='#')tSkipNum++;else{if(tSkipNum>0)tSkipNum--;elsebreak;}j--;}//去掉后半部分#，再比较s[i]!=t[j]if(i<0||j<0)break;//s或t已经遍历到终点if(s[i]!==t[j])returnfalse;i--;j--;}//说明s同时完成与t的遍历if(i==-1&&j==-1)returntrue;returnfalse;};
