LeetCode.1047-重複删除字元串中的所有相鄰重複項

這是小川的第389次更新，第419篇原創

01 看題和準備

今天介紹的是LeetCode算法題中Easy級别的第251題（順位題号是1047）。給定一個小寫字母的字元串

S

，重複删除兩個相鄰且相等的字母。

我們在

S

上反複删除，直到我們再也無法删除。

在完成所有此類重複删除後傳回最後一個字元串。保證答案是獨一無二的。

例如：

輸入："abbaca"

輸出："ca"

說明：在"abbaca"中我們可以删除"bb"，因為字母相鄰且相等，這是唯一可能的移動。這一舉動的結果是字元串是"aaca"，其中隻有"aa"是可能的，是以最後的字元串是"ca"。

注意：

• 1 <= S.length <= 20000
• S僅由英文小寫字母組成。

02 第一種解法

題目的意思是依次比較

S

中相鄰的兩個字母，如果相同，就删除掉，組成一個新的字元串，繼續剛才的操作，直到最後

S

中沒有相鄰的重複的字母。

思路：定義一個布爾類型變量

flag

，控制上一次周遊

S

中的字母時，是否存在相鄰的重複字母。使用兩層循環，外層控制是否可以繼續删除，内層周遊

S

中相鄰的字母，如果相同就删掉，這裡采取截取字元串的方式來生成新的字元串，同時将

flag

改為

true

，以便繼續外層循環。

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 第二種解法

我們還可以借助棧來實作，借助其後進先出的特性。

思路：周遊

S

中的字母，如果目前字母和棧頂的字母相等，就将棧頂的字母移除，如果不相等，就壓入棧頂，直到周遊完所有字母。最後将棧中的字母拼接到

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

來完成類似棧的操作。

思路：建立一個

StringBuilder

對象，周遊S中的字母，如果目前字母和

StringBuilder

中的最後一個字母相等，就将

StringBuilder

中的最後一個字母删除，否則就繼續往後拼接。

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

數組來實作。

思路：建立一個長度和

S

相等的

char

數組，周遊

S

中的字母，如果目前字母和

char

數組中的最後一個字母相等，就将索引前移，下次再往

char

數組中添加元素時，就會根據新的索引重新指派，起到移除重複字母的效果。

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 小結

算法專題目前已連續日更超過七個月，算法題文章257+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。

以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！