1047 Remove All Adjacent Duplicates In String 刪除字符串中的所有相鄰重復(fù)項(xiàng)

Description:
Given a string S of lowercase letters, a duplicate removal consists of choosing two adjacent and equal letters, and removing them.

We repeatedly make duplicate removals on S until we no longer can.

Return the final string after all such duplicate removals have been made. It is guaranteed the answer is unique.

Example:

Example 1:

Input: "abbaca"
Output: "ca"
Explanation:
For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move. The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".

Note:

1 <= S.length <= 20000
S consists only of English lowercase letters.

題目描述:
給出由小寫字母組成的字符串 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"。

提示：

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

思路:

參考LeetCode #20 Valid Parentheses 有效的括號(hào)
將字符壓入棧, 再比較, 相同的丟棄
時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(1)

代碼:
C++:

class Solution 
{
public:
    string removeDuplicates(string S) 
    {
        int top = 0;
        for (auto c : S)
        {
            if (!top or S[top - 1] != c) S[top++] = c;
            else top--;
        }
        S.resize(top);
        return S;
    }
};

Java:

class Solution {
    public String removeDuplicates(String S) {
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < S.length(); ++i) {
            if (result.length() == 0) result.append(S.charAt(i));
            else if (result.charAt(result.length() - 1) == S.charAt(i)) result.setLength(result.length() - 1);
            else result.append(S.charAt(i));
        }
        return  result.toString();
    }
}

Python:

class Solution:
    def removeDuplicates(self, S: str) -> str:
        s = []
        for c in S:
            if s and s[-1] == c:
                s.pop()
            else:
                s.append(c)
        return ''.join(s)