[Leetcode 1047] Remove All Adjacent Duplicates In String

原题说明

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 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.

解题思路

将需要返回的结果res当做一个stack，遍历S
每次比较当前的元素ch是否与res最后的元素（即栈顶）相同：
如果相同则将res最后的元素pop出去
如果不同则在res最后插入当前元素
最后返回res即可。

示例代码 (cpp)

class Solution {
public:
    string removeDuplicates(string S) {
        string res;
        for (const auto ch : S) {
            if (!res.empty() && res.back() == ch) {
                res.pop_back();
            } else {
                res.push_back(ch);
            }
        }
        return res;
    }
};

示例代码 (java)

class Solution {
    public String removeDuplicates(String s) {
        int i = 0, n = s.length();
        char[] res = s.toCharArray();
        for (int j = 0; j < n; ++j, ++i) {
            res[i] = res[j];
            if (i > 0 && res[i - 1] == res[i]) // count = 2
                i -= 2;
        }
        return new String(res, 0, i);
    }
}

示例代码 (python)

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

复杂度分析

时间复杂度: O(N)
空间复杂度: O(N) for Cpp and Python solution, O(1) for Java solution.

归纳总结

我们在Youtube上更新了视频讲解，欢迎关注！