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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。