這種匹配（消除）問題也是棧的擅長(zhǎng)所在！

844.比較含退格的字符串

給定 S 和 T 兩個(gè)字符串，當(dāng)它們分別被輸入到空白的文本編輯器后，判斷二者是否相等，并返回結(jié)果。# 代表退格字符。

注意：如果對(duì)空文本輸入退格字符，文本繼續(xù)為空。 示例 1：

• 輸入：S = "ab#c", T = "ad#c"
• 輸出：true
• 解釋：S 和 T 都會(huì)變成 “ac”。

示例 2：

• 輸入：S = "ab##", T = "c#d#"
• 輸出：true
• 解釋：S 和 T 都會(huì)變成 “”。

示例 3：

• 輸入：S = "a##c", T = "#a#c"
• 輸出：true
• 解釋：S 和 T 都會(huì)變成 “c”。

示例 4：

• 輸入：S = "a#c", T = "b"
• 輸出：false
• 解釋：S 會(huì)變成 “c”，但 T 仍然是 “b”。

思路

本文將給出 空間復(fù)雜度O(n)的棧模擬方法 以及空間復(fù)雜度是O(1)的雙指針方法。

普通方法（使用棧的思路）

這道題目一看就是要使用棧的節(jié)奏，這種匹配（消除）問題也是棧的擅長(zhǎng)所在，跟著一起刷題的同學(xué)應(yīng)該知道，在棧與隊(duì)列：匹配問題都是棧的強(qiáng)項(xiàng)，我就已經(jīng)提過了一次使用棧來做類似的事情了。

那么本題，確實(shí)可以使用棧的思路，但是沒有必要使用棧，因?yàn)樽詈蟊容^的時(shí)候還要比較棧里的元素，有點(diǎn)麻煩。

這里直接使用字符串string，來作為棧，末尾添加和彈出，string都有相應(yīng)的接口，最后比較的時(shí)候，只要比較兩個(gè)字符串就可以了，比比較棧里的元素方便一些。

代碼如下：

classSolution{
public:
boolbackspaceCompare(stringS,stringT){
strings;//當(dāng)棧來用
stringt;//當(dāng)棧來用
for(inti=0;iif(S[i]!='#')s+=S[i];
elseif(!s.empty()){
s.pop_back();

}
for(inti=0;iif(T[i]!='#')t+=T[i];
elseif(!t.empty()){
t.pop_back();
}
}
if(s==t)returntrue;//直接比較兩個(gè)字符串是否相等，比用棧來比較方便多了
returnfalse;
}
};

• 時(shí)間復(fù)雜度:O(n + m)， n為S的長(zhǎng)度，m為T的長(zhǎng)度 ，也可以理解是O(n)的時(shí)間復(fù)雜度
• 空間復(fù)雜度:O(n + m)

當(dāng)然以上代碼，大家可以發(fā)現(xiàn)有重復(fù)的邏輯處理S，處理T，可以把這塊公共邏輯抽離出來，代碼精簡(jiǎn)如下：

classSolution{
private:
stringgetString(conststring&S){
strings;
for(inti=0;iif(S[i]!='#')s+=S[i];
elseif(!s.empty()){
s.pop_back();
}
}
returns;
}
public:
boolbackspaceCompare(stringS,stringT){
returngetString(S)==getString(T);
}
};

性能依然是：

• 時(shí)間復(fù)雜度:O(n + m)
• 空間復(fù)雜度:O(n + m)

優(yōu)化方法（從后向前雙指針）

當(dāng)然還可以有使用 O(1) 的空間復(fù)雜度來解決該問題。

同時(shí)從后向前遍歷S和T（i初始為S末尾，j初始為T末尾），記錄#的數(shù)量，模擬消除的操作，如果#用完了，就開始比較S[i]和S[j]。

動(dòng)畫如下：

如果S[i]和S[j]不相同返回false，如果有一個(gè)指針（i或者j）先走到的字符串頭部位置，也返回false。

代碼如下：

classSolution{
public:
boolbackspaceCompare(stringS,stringT){
intsSkipNum=0;//記錄S的#數(shù)量
inttSkipNum=0;//記錄T的#數(shù)量
inti=S.size()-1;
intj=T.size()-1;
while(1){
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(i0||j0)break;//S或者T遍歷到頭了
if(S[i]!=T[j])returnfalse;
i--;j--;
}
//說明S和T同時(shí)遍歷完畢
if(i==-1&&j==-1)returntrue;
returnfalse;
}
};

• 時(shí)間復(fù)雜度：O(n + m)
• 空間復(fù)雜度：O(1)