LEETCODE 1209. Remove All Adjacent Duplicates in String II 解题思路分析

题目大意：

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

给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。

你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。

在执行完所有删除操作后，返回最终得到的字符串。

本题答案保证唯一。

示例 1：

输入：s = "abcd", k = 2
输出："abcd"
解释：没有要删除的内容。

示例 2：

输入：s = "deeedbbcccbdaa", k = 3
输出："aa"
解释： 
先删除 "eee" 和 "ccc"，得到 "ddbbbdaa"
再删除 "bbb"，得到 "dddaa"
最后删除 "ddd"，得到 "aa"

示例 3：

输入：s = "pbbcggttciiippooaais", k = 2
输出："ps"

提示：

• 1 <= s.length <= 10^5
• 2 <= k <= 10^4
• s 中只含有小写英文字母。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1209

解题思路分析：

这是一道典型使用Stack来求解的题目。循环字符串的每一个字符，如果当前字符与Stack中最后插入的字符不同，那么将当前字符插入到Stack中。如果相同，便要查看Stack中最后连续相同字符的长度加上当前字符是否等于题目给出的k，如果等于则将Stack中最后相同的部分pop出来。如果未达到k的长度，则将当前字符加入到Stack中。重复执行此步骤直到循环结束。

为了方便查看Stack最后有多少连续字符与当前字符相同，我们可以在新建另外一个Stack，保存最后连续相同字符的长度。

细节实现可以看下完整代码：

public String removeDuplicates(String s, int k) {
    Stack<Character> stack = new Stack<>(); // 排重的Stack
    Stack<Integer> stackLength = new Stack<>(); // 记录连续相同字符长度的Stack
    for(int i=0;i<s.length();i++){ // 循环每一个字符
        char c = s.charAt(i); // 当前字符
        // Stack为空或者当前字符与Stack上次插入的字符不相同
        if(stack.size()==0 || c != stack.peek()){
            stack.push(c); // 将当前字符插入到stack
            stackLength.push(1); // 当前字符连续长度为1
        }else{ // 当前字符与stack中前字符相同
            int sameLength = stackLength.pop()+1; // 连续相同字符的长度
            if(sameLength == k){ // 如果长度为k
                for(int j=1;j<k;j++){ // 删除连续相同的字符
                    stack.pop();
                }
            }else{ // 长度小于k
                // 更新连续相同字符长度
                stackLength.push(sameLength);
                stack.push(c); // 将当前字符加入到stack
            }
        }
    }
    // 将stack剩下的元素组成返回值。注意需要反转字符串
    StringBuilder res=new StringBuilder();
    while(stack.size()>0){
        res.append(stack.pop());
    }
    return res.reverse().toString();
}

本题是典型的Stack题目。如果将Stack变成数组来实现将大幅提高运行速度。这里为了方便理解，并没有做出上述优化。

本题解法运行时间为39ms。

Runtime: 39 ms, faster than 36.81% of Java online submissions for Remove All Adjacent Duplicates in String II.

Memory Usage: 38.4 MB, less than 100.00% of Java online submissions for Remove All Adjacent Duplicates in String II.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1209-remove-all-adjacent-duplicates-in-string-ii-解题思路分析/