Skip to content

Latest commit

 

History

History
529 lines (448 loc) · 15.2 KB

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

File metadata and controls

529 lines (448 loc) · 15.2 KB
Raw

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

匹配问题都是栈的强项

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

力扣题目链接

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

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

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

示例：

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

提示：

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

算法公开课

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

思路

正题

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

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

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

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

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

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

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

从栈中弹出剩余元素，此时是字符串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 {
    stack := make([]rune, 0)
    for _, val := range s {
        if len(stack) == 0 || val != stack[len(stack)-1] {
            stack = append(stack, val)
        } else {
            stack = stack[:len(stack)-1]
        }
    }
    var res []rune
    for len(stack) != 0 { // 将栈中元素放到result字符串汇总
        res = append(res, stack[len(stack)-1])
        stack = stack[:len(stack)-1]
    }
    // 此时字符串需要反转一下
    l, r := 0, len(res)-1
    for l < r {
        res[l], res[r] = res[r], res[l]
        l++
        r--
    }
    return string(res)
}

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

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()
    }
}

Ruby

def remove_duplicates(s)
  #数组模拟栈
  stack = []
  s.each_char do |chr|
    if stack.empty?
      stack.push chr
    else
      head = stack.pop 
      #重新进栈
      stack.push head, chr if head != chr
    end
  end

  return stack.join
end