這是小川的第389次更新泻云，第419篇原創(chuàng)
01 看題和準備
今天介紹的是LeetCode算法題中Easy級別的第251題（順位題號是1047）。給定一個小寫字母的字符串S碟渺，重復刪除兩個相鄰且相等的字母惊窖。
我們在S上反復刪除，直到我們再也無法刪除摆昧。
在完成所有此類重復刪除后返回最后一個字符串。保證答案是獨一無二的蜒程。
例如：
輸入："abbaca"
輸出："ca"
說明：在"abbaca"中我們可以刪除"bb"绅你，因為字母相鄰且相等，這是唯一可能的移動昭躺。這一舉動的結果是字符串是"aaca"忌锯，其中只有"aa"是可能的，所以最后的字符串是"ca"窍仰。
注意：
1 <= S.length <= 20000
S僅由英文小寫字母組成汉规。
02 第一種解法
題目的意思是依次比較S中相鄰的兩個字母，如果相同驹吮，就刪除掉针史，組成一個新的字符串，繼續(xù)剛才的操作碟狞，直到最后S中沒有相鄰的重復的字母啄枕。
思路：定義一個布爾類型變量flag，控制上一次遍歷S中的字母時族沃，是否存在相鄰的重復字母频祝。使用兩層循環(huán)，外層控制是否可以繼續(xù)刪除脆淹，內層遍歷S中相鄰的字母常空，如果相同就刪掉，這里采取截取字符串的方式來生成新的字符串盖溺，同時將flag改為true漓糙，以便繼續(xù)外層循環(huán)。
public String removeDuplicates(String S) {
boolean flag = true;
while (flag) {
flag = false;
int n = S.length()-1;
for (int i=0; i<n; i++) {
if (S.charAt(i) == S.charAt(i+1)) {
S = S.substring(0, i)+
S.substring(i+2, S.length());
flag = true;
break;
}
}
}
return S;
}
03 第二種解法
我們還可以借助棧來實現(xiàn)烘嘱，借助其后進先出的特性昆禽。
思路：遍歷S中的字母蝗蛙，如果當前字母和棧頂?shù)淖帜赶嗟龋蛯ｍ數(shù)淖帜敢瞥肀睿绻幌嗟燃窆瑁蛪喝霔ｍ敚钡奖闅v完所有字母盗棵。最后將棧中的字母拼接到StringBuilder中去壮韭，轉為字符串時，要反轉漾根，因為最先出棧的字母是S中較后面的泰涂。
public String removeDuplicates2(String S) {
Stack<Character> stack = new Stack<Character>();
int n = S.length();
for (int i=0; i<n; i++) {
if (!stack.isEmpty() && S.charAt(i) == stack.peek()) {
stack.pop();
} else {
stack.push(S.charAt(i));
}
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
return sb.reverse().toString();
}
04 第三種解法
同樣借助棧的思路鲫竞，但是我們可以不使用棧辐怕，通過StringBuilder來完成類似棧的操作。
思路：創(chuàng)建一個StringBuilder對象从绘，遍歷S中的字母寄疏，如果當前字母和StringBuilder中的最后一個字母相等，就將StringBuilder中的最后一個字母刪除僵井，否則就繼續(xù)往后拼接陕截。
public String removeDuplicates3(String S) {
StringBuilder sb = new StringBuilder();
int n = S.length();
for (int i=0; i<n; i++) {
int size = sb.length();
if (size > 0 && sb.charAt(size-1) == S.charAt(i)) {
sb.deleteCharAt(size-1);
} else {
sb.append(S.charAt(i));
}
}
return sb.toString();
}
05 第四種解法
同樣借助棧的思路，我們還可以利用char數(shù)組來實現(xiàn)批什。
思路：創(chuàng)建一個長度和S相等的char數(shù)組农曲，遍歷S中的字母，如果當前字母和char數(shù)組中的最后一個字母相等驻债，就將索引前移乳规，下次再往char數(shù)組中添加元素時，就會根據(jù)新的索引重新賦值合呐，起到移除重復字母的效果暮的。
public String removeDuplicates4(String S) {
int n = S.length(), index = 0;
char[] arr = new char[n];
for (int i=0; i<n; i++) {
if (index > 0 && arr[index-1] == S.charAt(i)) {
index--;
} else {
arr[index++] = S.charAt(i);
}
}
return new String(arr, 0, index);
}
06 小結
算法專題目前已連續(xù)日更超過七個月，算法題文章257+篇淌实，公眾號對話框回復【數(shù)據(jù)結構與算法】冻辩、【算法】、【數(shù)據(jù)結構】中的任一關鍵詞拆祈，獲取系列文章合集恨闪。
以上就是全部內容，如果大家有什么好的解法思路放坏、建議或者其他問題咙咽，可以下方留言交流，點贊轻姿、留言犁珠、轉發(fā)就是對我最大的回報和支持逻炊！
