LeetCode1047. 删除字符串中的所有相邻重复项

快来打我* 2022-11-06 11:55 34阅读 0赞

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string][https_leetcode-cn.com_problems_remove-all-adjacent-duplicates-in-string]  
难度：`简单`  
题目描述

> 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。  
> 在 S 上反复执行重复项删除操作，直到无法继续删除。  
> 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

> 输入：“abbaca”  
> 输出：“ca”

解释：

> 例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。

提示：

> 1 <= S.length <= 20000  
> S 仅由小写英文字母组成。

暴力解：

class Solution { 
    public:
        string removeDuplicates(string S) { 
            int n=S.length();
            if(n<2){ 
                return S;
            }
            string::iterator it;
            for(int i=0;i<S.length()-1;){ 
                if(S.length()<2){ 
                    return S;
                }
                if(S[i]==S[i+1]){ 
                    S.erase(i,2);
                    i=0;
                }else{ 
                    i++;
                }
            }
            return S;
        }
    };

栈：

class Solution { 
    public:
        string removeDuplicates(string S) { 
            int n=S.length();
            if(n<2){ 
                return S;
            }
            string ans;
            for(int i=0;i<S.length();i++){ 
                if(ans.back()!=S[i]||ans.empty()){ 
                    ans.push_back(S[i]);
                }else{ 
                    ans.pop_back();
                }
            }
            return ans;
        }
    };

[https_leetcode-cn.com_problems_remove-all-adjacent-duplicates-in-string]: https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string