題目：
給出由小寫字母組成的字符串 S瘩扼，重復(fù)項(xiàng)刪除操作會(huì)選擇兩個(gè)相鄰且相同的字母睛藻，并刪除它們。
在 S 上反復(fù)執(zhí)行重復(fù)項(xiàng)刪除操作邢隧，直到無法繼續(xù)刪除店印。
在完成所有重復(fù)項(xiàng)刪除操作后返回最終的字符串。答案保證唯一倒慧。
示例：
輸入："abbaca"
輸出："ca"
解釋：
例如按摘，在 "abbaca" 中，我們可以刪除 "bb" 由于兩字母相鄰且相同纫谅，這是此時(shí)唯一可以執(zhí)行刪除操作的重復(fù)項(xiàng)炫贤。之后我們得到字符串 "aaca"，其中又只有 "aa" 可以執(zhí)行重復(fù)項(xiàng)刪除操作付秕，所以最后的字符串為 "ca"兰珍。
思路一：
和消消樂很相似，兩個(gè)相鄰字符一樣消掉询吴。
由于都是小寫掠河，總共會(huì)有26組字符串出現(xiàn)會(huì)被消除。'aa'到'zz'猛计，存儲(chǔ)到set中唠摹。
當(dāng)消除前的字符串長(zhǎng)度!=消除后的字符串長(zhǎng)度，說明還有可消除的奉瘤。
代碼如下：
public String removeDuplicates1(String S) {
// 準(zhǔn)備替換字符set
// 'a'= 97 , 'z'=122
Set<String> set = new HashSet<String>();
for (int i = 97; i <= 122; i++) {
char c = (char) i;
set.add("" + c + c);
}
int preLen = 0;// 替換前字符串長(zhǎng)度
while (preLen != S.length()) {//判斷換前長(zhǎng)度是否和當(dāng)前長(zhǎng)度相等
preLen = S.length();
for (String s : set) {
S = S.replace(s, "");
}
}
return S;
}
思路二：
由于是相鄰相同會(huì)消除勾拉，使用棧來存放每個(gè)字符。
創(chuàng)建棧，入棧前先比較棧頂字符和即將入棧字符是否一致藕赞。
一致則移除棧頂字符成肘，不一致則添加進(jìn)去。
需要注意棧為空的情況斧蜕。
代碼如下：
public boolean backspaceCompare(String S, String T) {
Stack<Character> stackS = new Stack<Character>();
Stack<Character> stackT = new Stack<Character>();
int len = S.length() > T.length() ? S.length() : T.length();
for (int i = 0; i < len; i++) {
if (i < S.length()) {
char s = S.charAt(i);
if ('#' == s) {
if (!stackS.isEmpty())
stackS.pop();
} else {
stackS.push(s);
}
}
if (i < T.length()) {
char t = T.charAt(i);
if ('#' == t) {
if (!stackT.isEmpty())
stackT.pop();
} else {
stackT.push(t);
}
}
}
return stackS.equals(stackT);
}
-------------------------------小白學(xué)算法
