题目
题目来源leetcode
leetcode地址：1047. 删除字符串中的所有相邻重复项，难度：简单。
题目描述(摘自leetcode)：
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。 在 S 上反复执行重复项删除操作，直到无法继续删除。 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。 示例： 输入："abbaca" 输出："ca" 解释： 例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。 提示： 1 <= S.length <= 20000 S 仅由小写英文字母组成。
本地调试代码：
class Solution { public String removeDuplicates(String s) { ... } public static void main(String[] args) { System.out.println(new Solution().removeDuplicates("abbaca")); } }
题解
NO1：栈解决
思路：遍历字符时，每次先判断当前栈顶元素是否与要入栈的元素相同，如果相同出栈，不相同入栈。最后将栈中的字符进行一一拼接返回。
示例："abbaca" stack=[] ① 字符'a'，当前栈为空直接入栈 stack=['a'] ② 字符'b'，栈不为空，与栈顶元素a比较，不相同入栈 stack=['a','b'] ③ 字符'b'，栈不为空，与栈顶元素b比较，相同出栈 stack=['a'] ④ 字符'a'，栈不为空，与栈顶元素b比较，相同出栈 stack=[] ⑤ 字符'c'，当前栈为空直接入栈 stack=['c'] ⑥ 字符'a'，栈不为空，与栈顶元素c比较，不相同入栈 stack=['a','c'] 最终从前往往后将元素移出进行拼接，返回"ac"
代码：
class Solution { public String removeDuplicates(String s) { Deque<Character> stack = new LinkedList<>(); for (char c : s.toCharArray()) { //当前栈不为空，且栈顶与当前字符相同出栈 if(!stack.isEmpty() && stack.peek() == c){ stack.pop(); }else{//否则直接入栈 stack.push(c); } } StringBuilder str = new StringBuilder(); while(!stack.isEmpty()){ str = str.append(stack.pollLast()); } return str.toString(); } }
NO2：字符串作栈
思路：使用字符串作栈的好处就是可以省去上面提交中拼接的操作，最终留在字符串里的就是要返回出去的。
示例："abbaca" str="" top=-1 ① 字符'a' 字符串(栈)为空，直接拼接 str="a" top=0 ② 字符'b' 字符串(栈)不为空，与栈顶不相同，直接拼接 str="ab" top=1 ③ 字符'b' 字符串(栈)不为空，与栈顶相同，删除指定元素 str="a" top=0 ④ 字符'a' 字符串(栈)不为空，与栈顶相同，删除指定元素 str="" top=-1 ⑤ 字符'c' 字符串(栈)为空，直接拼接 str="c" top=0 ⑥ 字符'b' 字符串(栈)不为空，与栈顶不相同，直接拼接 str="ca" top=1 最终直接返回str="ca"
代码：
class Solution { //目的是拿到不重复的字符拼接内容 public String removeDuplicates(String s) { //直接来拿字符串来作为栈进行操作，最终剩下来的就是不重复的 StringBuilder str = new StringBuilder(); int top = -1; for (char c : s.toCharArray()) { if(top >= 0 && c == str.charAt(top)){ str.deleteCharAt(top--); }else{ str.append(c); top++; } } return str.toString(); } }
NO3、双指针(原数组上操作)
思路：直接对原数组进行操作，不相邻的重复元素直接覆盖旧元素，最终直接截取原数组指定长度内容返回。
fast指针用来进行遍历一遍字符串的，[0,slow)永远表示的是非相邻重复项 示例：s="abbaca" slow=0,fast=0 ① 字符'a' s[0]=s[0] (s="abbaca") slow=1,fast=1 | [0,slow)=> "a" ② 字符'b' s[1]=s[1] (s="abbaca") slow=2,fast=2 | [0,slow)=> "ab" ③ 字符'b' s[2]=s[2] (s="abbaca")(s[2]==s[1] => b=b重复，slow-1) slow=1,fast=3 | [0,slow)=> "a" ④ 字符'a' s[1]=s[3] (s="aabaca")(s[1]==s[0] => a=a重复，slow-1) slow=0,fast=4 | [0,slow)=> "" ⑤ 字符'c' s[0]=s[4] (s="cabaca")(slow=0，slow+1) slow=1,fast=5 | [0,slow)=> "c" ⑥ 字符'a' s[1]=s[5] (s="cabaca")(s[1]!=s[0]，slow++) slow=1,fast=4 | [0,slow)=> "ca" 最终直接返回"ca"即可
代码：
//快慢指针，时间复杂度O(n)，空间复杂度O(1) public String removeDuplicates(String s) { //定义双指针 int slow = 0;//左指针的目的是①检测是否有相等，有后退，无前进。②实时更新当前最新位置值(方便下次进行对比以及旧值的覆盖，旧的值已无用) int fast = 0;//右指针负责的工作是进行遍历作用 char[] chars = s.toCharArray(); while(fast < s.length()){ chars[slow] = chars[fast]; if(slow > 0 && chars[slow]==chars[slow-1]){ slow--; }else{ slow++; } fast++; } //[0,slow)区间值 return new String(chars,0,slow); }
