序
本文主要記錄一下leetcode棧之比較含退格的字符串
題目
給定 S 和 T 兩個字符串曙蒸，當它們分別被輸入到空白的文本編輯器后，判斷二者是否相等茎刚，并返回結果。 # 代表退格字符。
注意：如果對空文本輸入退格字符间影，文本繼續(xù)為空。
示例 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) 的空間復雜度解決該問題嗎愈犹？
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/backspace-string-compare
著作權歸領扣網(wǎng)絡所有键科。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權，非商業(yè)轉(zhuǎn)載請注明出處。
題解
class Solution {
public boolean backspaceCompare(String S, String T) {
Stack<Character> stackS = processBackspace(S);
Stack<Character> stackT = processBackspace(T);
if(stackS.size()!=stackT.size()){
return false;
}
while (!stackS.isEmpty()){
if(stackS.pop()!=stackT.pop()){
return false;
}
}
return true;
}
public Stack<Character> processBackspace(String str) {
Stack<Character> result = new Stack<>();
for(char data: str.toCharArray()){
if(data == '#'){
if(!result.isEmpty()){
result.pop();
}
} else {
result.push(data);
}
}
return result;
}
}
小結
這里借助棧勋颖，遍歷string的char嗦嗡，遇到#時在棧不為空的時候pop一下，非#時則push數(shù)據(jù)到棧中饭玲；之后對比兩個棧的元素來判斷是否相等侥祭。
