参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

匹配问题都是栈的强项

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

力扣题目链接

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

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

提示：

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

思路

《代码随想录》算法视频公开课：栈的好戏还要继续！| LeetCode：1047. 删除字符串中的所有相邻重复项，相信结合视频在看本篇题解，更有助于大家对本题的理解。

正题

本题要删除相邻相同元素，相对于20. 有效的括号来说其实也是匹配问题，20. 有效的括号是匹配左右括号，本题是匹配相邻元素，最后都是做消除的操作。

本题也是用栈来解决的经典题目。

那么栈里应该放的是什么元素呢？

我们在删除相邻重复项的时候，其实就是要知道当前遍历的这个元素，我们在前一位是不是遍历过一样数值的元素，那么如何记录前面遍历过的元素呢？

所以就是用栈来存放，那么栈的目的，就是存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下我们是不是遍历过相同数值的相邻元素。

然后再去做对应的消除操作。如动画所示：

从栈中弹出剩余元素，此时是字符串ac，因为从栈里弹出的元素是倒序的，所以再对字符串进行反转一下，就得到了最终的结果。

C++代码 :

class Solution {
public:
    string removeDuplicates(string S) {
        stack<char> st;
        for (char s : S) {
            if (st.empty() || s != st.top()) {
                st.push(s);
            } else {
                st.pop(); // s 与 st.top()相等的情况
            }
        }
        string result = "";
        while (!st.empty()) { // 将栈中元素放到result字符串汇总
            result += st.top();
            st.pop();
        }
        reverse (result.begin(), result.end()); // 此时字符串需要反转一下
        return result;

    }
};

时间复杂度: O(n)
空间复杂度: O(n)

当然可以拿字符串直接作为栈，这样省去了栈还要转为字符串的操作。

代码如下：

class Solution {
public:
    string removeDuplicates(string S) {
        string result;
        for(char s : S) {
            if(result.empty() || result.back() != s) {
                result.push_back(s);
            }
            else {
                result.pop_back();
            }
        }
        return result;
    }
};

时间复杂度: O(n)
空间复杂度: O(1)，返回值不计空间复杂度

题外话

这道题目就像是我们玩过的游戏对对碰，如果相同的元素挨在一起就要消除。

可能我们在玩游戏的时候感觉理所当然应该消除，但程序又怎么知道该如何消除呢，特别是消除之后又有新的元素可能挨在一起。

此时游戏的后端逻辑就可以用一个栈来实现（我没有实际考察对对碰或者爱消除游戏的代码实现，仅从原理上进行推断）。

游戏开发可能使用栈结构，编程语言的一些功能实现也会使用栈结构，实现函数递归调用就需要栈，但不是每种编程语言都支持递归，例如：

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

相信大家应该遇到过一种错误就是栈溢出，系统输出的异常是Segmentation fault（当然不是所有的Segmentation fault 都是栈溢出导致的），如果你使用了递归，就要想一想是不是无限递归了，那么系统调用栈就会溢出。

而且在企业项目开发中，尽量不要使用递归！在项目比较大的时候，由于参数多，全局变量等等，使用递归很容易判断不充分return的条件，非常容易无限递归（或者递归层级过深），造成栈溢出错误（这种问题还不好排查！）

其他语言版本

Java：

使用 Deque 作为堆栈

class Solution {
    public String removeDuplicates(String S) {
        //ArrayDeque会比LinkedList在除了删除元素这一点外会快一点
        //参考：https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist
        ArrayDeque<Character> deque = new ArrayDeque<>();
        char ch;
        for (int i = 0; i < S.length(); i++) {
            ch = S.charAt(i);
            if (deque.isEmpty() || deque.peek() != ch) {
                deque.push(ch);
            } else {
                deque.pop();
            }
        }
        String str = "";
        //剩余的元素即为不重复的元素
        while (!deque.isEmpty()) {
            str = deque.pop() + str;
        }
        return str;
    }
}

拿字符串直接作为栈，省去了栈还要转为字符串的操作。

class Solution {
    public String removeDuplicates(String s) {
        // 将 res 当做栈
        // 也可以用 StringBuilder 来修改字符串，速度更快
        // StringBuilder res = new StringBuilder();
        StringBuffer res = new StringBuffer();
        // top为 res 的长度
        int top = -1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 当 top > 0,即栈中有字符时，当前字符如果和栈中字符相等，弹出栈顶字符，同时 top--
            if (top >= 0 && res.charAt(top) == c) {
                res.deleteCharAt(top);
                top--;
            // 否则，将该字符 入栈，同时top++
            } else {
                res.append(c);
                top++;
            }
        }
        return res.toString();
    }
}

拓展：双指针

class Solution {
    public String removeDuplicates(String s) {
        char[] ch = s.toCharArray();
        int fast = 0;
        int slow = 0;
        while(fast < s.length()){
            // 直接用fast指针覆盖slow指针的值
            ch[slow] = ch[fast];
            // 遇到前后相同值的，就跳过，即slow指针后退一步，下次循环就可以直接被覆盖掉了
            if(slow > 0 && ch[slow] == ch[slow - 1]){
                slow--;
            }else{
                slow++;
            }
            fast++;
        }
        return new String(ch,0,slow);
    }
}

Python：

# 方法一，使用栈
class Solution:
    def removeDuplicates(self, s: str) -> str:
        res = list()
        for item in s:
            if res and res[-1] == item:
                res.pop()
            else:
                res.append(item)
        return "".join(res)  # 字符串拼接

# 方法二，使用双指针模拟栈，如果不让用栈可以作为备选方法。
class Solution:
    def removeDuplicates(self, s: str) -> str:
        res = list(s)
        slow = fast = 0
        length = len(res)

        while fast < length:
            # 如果一样直接换，不一样会把后面的填在slow的位置
            res[slow] = res[fast]
            
            # 如果发现和前一个一样，就退一格指针
            if slow > 0 and res[slow] == res[slow - 1]:
                slow -= 1
            else:
                slow += 1
            fast += 1
            
        return ''.join(res[0: slow])

Go：

func removeDuplicates(s string) string {
    var stack []byte
    for i := 0; i < len(s);i++ {
        // 栈不空 且 与栈顶元素不等
        if len(stack) > 0 && stack[len(stack)-1] == s[i] {
            // 弹出栈顶元素 并 忽略当前元素(s[i])
            stack = stack[:len(stack)-1]
        }else{
            // 入栈
            stack = append(stack, s[i])
        }
    }
    return string(stack)
}

javaScript:

法一：使用栈

var removeDuplicates = function(s) {
    const result = []
    for(const i of s){
        if(i === result[result.length-1]){
            result.pop()
        }else{
            result.push(i)
        }
    }
    return result.join('')
};

法二：双指针（模拟栈）

// 原地解法（双指针模拟栈）
var removeDuplicates = function(s) {
    s = [...s];
    let top = -1; // 指向栈顶元素的下标
    for(let i = 0; i < s.length; i++) {
        if(top === -1 || s[top] !== s[i]) { // top === -1 即空栈
            s[++top] = s[i]; // 入栈
        } else {
            top--; // 推出栈
        }
    }
    s.length = top + 1; // 栈顶元素下标 + 1 为栈的长度
    return s.join('');
};

TypeScript：

function removeDuplicates(s: string): string {
    const helperStack: string[] = [];
    let i: number = 0;
    while (i < s.length) {
        let top: string = helperStack[helperStack.length - 1];
        if (top === s[i]) {
            helperStack.pop();
        } else {
            helperStack.push(s[i]);
        }
        i++;
    }
    let res: string = '';
    while (helperStack.length > 0) {
        res = helperStack.pop() + res;
    }
    return res;
};

C: 方法一：使用栈

char * removeDuplicates(char * s){
    //求出字符串长度
    int strLength = strlen(s);
    //开辟栈空间。栈空间长度应为字符串长度+1（为了存放字符串结束标志'\0'）
    char* stack = (char*)malloc(sizeof(char) * strLength + 1);
    int stackTop = 0;

    int index = 0;
    //遍历整个字符串
    while(index < strLength) {
        //取出当前index对应字母，之后index+1
        char letter = s[index++];
        //若栈中有元素，且栈顶字母等于当前字母（两字母相邻）。将栈顶元素弹出
        if(stackTop > 0 && letter == stack[stackTop - 1])
            stackTop--;
        //否则将字母入栈
        else
            stack[stackTop++] = letter;
    }
    //存放字符串结束标志'\0'
    stack[stackTop] = '\0';
    //返回栈本身作为字符串
    return stack;
}

方法二：双指针法

char * removeDuplicates(char * s){
    //创建快慢指针
    int fast = 0;
    int slow = 0;
    //求出字符串长度
    int strLength = strlen(s);
    //遍历字符串
    while(fast < strLength) {
        //将当前slow指向字符改为fast指向字符。fast指针+1
        char letter = s[slow] = s[fast++];
        //若慢指针大于0，且慢指针指向元素等于字符串中前一位元素，删除慢指针指向当前元素
        if(slow > 0 && letter == s[slow - 1])
            slow--;
        else
            slow++;
    }
    //在字符串结束加入字符串结束标志'\0'
    s[slow] = 0;
    return s;
}

Swift：

func removeDuplicates(_ s: String) -> String {
    var stack = [Character]()
    for c in s {
        if stack.last == c {
            stack.removeLast()
        } else {
            stack.append(c)
        }
    }
    return String(stack)
}

C#:

public string RemoveDuplicates(string s) {
        //拿字符串直接作为栈，省去了栈还要转为字符串的操作
        StringBuilder res = new StringBuilder();

        foreach(char c in s){
            if(res.Length > 0 && res[res.Length-1] == c){
                res.Remove(res.Length-1, 1);
            }else{
                res.Append(c);
            }
        }
       
        return res.ToString();
    }

PHP:

class Solution {
    function removeDuplicates($s) {
        $stack = new SplStack();
        for($i=0;$i<strlen($s);$i++){
            if($stack->isEmpty() || $s[$i] != $stack->top()){
                $stack->push($s[$i]);
            }else{
               $stack->pop(); 
            }
        }

        $result = "";
        while(!$stack->isEmpty()){
            $result.= $stack->top();
            $stack->pop();
        }
        
        // 此时字符串需要反转一下
        return strrev($result);
    }
}

Scala:

object Solution {
  import scala.collection.mutable
  def removeDuplicates(s: String): String = {
    var stack = mutable.Stack[Int]()
    var str = "" // 保存最终结果
    for (i <- s.indices) {
      var tmp = s(i)
      // 如果栈非空并且栈顶元素等于当前字符，那么删掉栈顶和字符串最后一个元素
      if (!stack.isEmpty && tmp == stack.head) {
        str = str.take(str.length - 1)
        stack.pop()
      } else {
        stack.push(tmp)
        str += tmp
      }
    }
    str
  }
}

rust:

impl Solution {
    pub fn remove_duplicates(s: String) -> String {
        let mut stack = vec![];
        let mut chars: Vec<char> = s.chars().collect();
        while let Some(c) = chars.pop() {
            if stack.is_empty() || stack[stack.len() - 1] != c {
                stack.push(c);
            } else {
                stack.pop();
            }
        }
        stack.into_iter().rev().collect()
    }
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

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

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

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

思路

正题

题外话

其他语言版本

Files

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

Latest commit

History

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

File metadata and controls

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

思路

正题

题外话

其他语言版本