leetcode 1047 - Remove All Adjacent Duplicates In String

題目
#

leetcode 1047 - Remove All Adjacent Duplicates In String(題目說明請點連結)

題目簡述
#

給定一個字串，重複移除相鄰且相等的字符，直到無法再移除為止。返回最終的字串。

Example 1:

Input: s = "abbaca"
Output: "ca"
Explanation: 在 "abbaca" 中，我們可以移除 "bb"，因為字母相鄰且相等。移除後的結果是 "aaca"，然後再移除 "aa"，最終字串是 "ca"。

Example 2:

Input: s = "azxxzy"
Output: "ay"
Explanation: 在 "azxxzy" 中，我們可以移除 "xx"，然後移除 "zz"，最終字串是 "ay"。

解題思路
#

輸入為一個字串，輸入為一個去除相鄰重複字元後的字串。
這題可以用Two pointors 的解法去實作。

以下面為例子：

分別用i、j二個指針，i為遍歷新字元的指針，j為判斷條件與搜索的答案。

步驟	字串狀態	指針位置	操作說明
Step 1	abbaca	i=0, j=0	i和j同時從0開始，覆蓋字元
	abbaca		同時前進覆蓋
Step 2	abbaca	i=2, j=1	遇到j當前位置與j-1位置重複
	abbaca		j退回到j-2位置(即0)
	abbaca	j=0	去除重複字元後繼續
Step 3	abbaca	i=3, j=1	繼續同時往下覆蓋
	aabaca		此時j、j-1位置又重複
	aabaca	j=-1	j退回到-1位置
Step 4	abbaca	i=4, j=0	繼續覆蓋，j從0開始
	cabaca		二指針繼續同時前進
Step 5	abbaca	i=5, j=1	i跑到最後一個位置
	cabaca		遍歷完成

完整程式碼
#

java

class Solution {
   public String removeDuplicates(String s) {
        int j = 0; // 初始化指針 j，用於記錄結果字符的位置
        char[] res = s.toCharArray(); // 將字串轉換為字符數組
        for(int i = 0; i < s.length(); ++i, ++j) { // 遍歷字符數組，i和j同時前進
            res[j] = res[i]; // 將當前字符賦值給 j 指針位置

            if(j > 0 && res[j] == res[j-1]) { // 如果當前字符和前一個字符相同
                j -= 2; // j 指針回退兩步，去除重複的字符
            }
        }
        return new String(res, 0, j); // 返回去重後的字串，只取前j個字符
    }
}

時間複雜度
#

時間複雜度：O(n)，其中 n 是字串的長度，因為每個字元最多只會被處理兩次（進出j指針）。
空間複雜度：O(n)，用於存儲字符數組 res。

Stack解法
#

其實最一開始的直覺是想到用 stack 去解這道題，
運用LIFO(Last In First Out)到機制，把給個字元分別放到Stack去做比較，
每次就檢查相鄰的二個值是否一致;
1.要放進Stack的值
2.Stack中最上面的那個值

Stack : ab
Put in : baca

相同就Stock pop出去，不相同就放進去繼續比較。
結束後就能拿到去除重複的字元Stack，在組成字串即為答案。

java

class Solution {
   public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>(); // 初始化一個Stack
        char[] chars = s.toCharArray(); // 將字串轉換為字符數組
        for(char c : chars){ // 遍歷字符數組
            if(!stack.isEmpty() && stack.peek() == c){ // 如果Stack不為空且Stack頂字符與當前字符相同
                stack.pop(); // 彈出Stack頂字符
            }else {
                stack.push(c); // 否則將當前字符壓入Stack
            }
        }

        StringBuilder result = new StringBuilder(); // 初始化結果字串
        for (char c : stack) { // 遍歷Stack
            result.append(c); // 將字符添加到結果字串
        }

        return result.toString(); // 返回結果字串
    }
}