1:问题描述

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

2:解题思路

用栈解决，空间复杂度O(n)，空间复杂度O(n)

3:Java代码

  1.    public String removeDuplicates(String S) {
  2.         Stack<Character> st = new Stack<>();
  3.         for (int i = 0; i < S.length(); i++) {
  4.             if (!st.empty() && S.charAt(i) == st.peek()) {
  5.                 st.pop();
  6.             } else {
  7.                 st.add(S.charAt(i));
  8.             }
  9.         }
  10.         StringBuilder res = new StringBuilder();
  11.         for (Character c : st) {
  12.             res.append(c);
  13.         }
  14.         return res.toString();
  15.     }

4:Go版本代码

  1. // 直接用切片实现
  2. func removeDuplicates(S string) string {
  3.     stack := []byte{}
  4.     for i := range S {
  5.         if len(stack) > 0 && stack[len(stack)-1] == S[i] {
  6.             stack = stack[:len(stack)-1]
  7.         } else {
  8.             stack = append(stack, S[i])
  9.         }
  10.     }
  11.     return string(stack)
  12. }