题目地址(1047. 删除字符串中的所有相邻重复项)

https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/

题目描述

  1. 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
  3. 在 S 上反复执行重复项删除操作，直到无法继续删除。
  5. 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
  9. 示例：
  11. 输入："abbaca"
  12. 输出："ca"
  13. 解释：
  14. 例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
  19. 提示：
  21. 1 <= S.length <= 20000
  22. S 仅由小写英文字母组成。

前置知识


公司

  • 暂无

思路

本质上是使用栈来做这道题 但是这道题可以使用stringbulider来充当栈
这题和上题匹配括号差不多 如果栈中的字母和当前正要入栈的相同 就将栈中的字母弹出 如果不相同就压入栈 最后循环结束后就只剩下不相同的元素了
1047.删除字符串中的所有相邻重复项.gif

代码

  • 语言支持：Java

Java Code:

  1. class Solution {
  2.         public String removeDuplicates(String s) {
  3.             StringBuilder sb = new StringBuilder();
  4.             char temp ;
  5.             int len = -1;
  6.             for (int i = 0; i < s.length(); i++) {
  7.                 temp = s.charAt(i);
  8.                 //当sb长度大于等于0 并且sb当前的字符等于temp时 就弹出栈并使长度--
  9.                 if (len >= 0 && sb.charAt(len) == temp) {
  10.                     sb.deleteCharAt(len);
  11.                     len--;
  12.                 }else {
  13.                     //反之 字符不等时就使字符压入栈 并使长度++
  14.                     sb.append(temp);
  15.                     len++;
  16.                 }
  17.             }
  18.             return sb.toString();
  19.         }
  20.     }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：1047. 删除字符串中的所有相邻重复项 - 图2#card=math&code=O%28n%29&id=LFp63)
  • 空间复杂度：1047. 删除字符串中的所有相邻重复项 - 图3#card=math&code=O%28n%29&id=IRLVu)