[LeetCode] Remove Duplicate Letters 移除重复字母

简介:

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:

Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

这道题让我们移除重复字母,使得每个字符只能出现一次,而且结果要按字母顺序排,前提是不能打乱其原本的相对位置。我们的解题思路是:先建立一个哈希表来统计每个字母出现的次数,还需要一个visited数字来纪录每个字母是否被访问过,我们遍历整个字符串,对于遍历到的字符,先在哈希表中将其值减一,然后看visited中是否被访问过,若访问过则继续循环,说明该字母已经出现在结果中并且位置已经安排妥当。如果没访问过,我们和结果中最后一个字母比较,如果该字母的ASCII码小并且结果中的最后一个字母在哈希表中的值不为0(说明后面还会出现这个字母),那么我们此时就要在结果中删去最后一个字母且将其标记为未访问,然后加上当前遍历到的字母,并且将其标记为已访问,以此类推直至遍历完整个字符串s,此时结果里的字符串即为所求。这里有个小技巧,我们一开始给结果字符串res中放个"0",就是为了在第一次比较时方便,如果为空就没法和res中的最后一个字符比较了,而‘0’的ASCII码要小于任意一个字母的,所以不会有问题。最后我们返回结果时再去掉开头那个‘0’即可,参见代码如下:

class Solution {
public:
    string removeDuplicateLetters(string s) {
        int m[256] = {0}, visited[256] = {0};
        string res = "0";
        for (auto a : s) ++m[a];
        for (auto a : s) {
            --m[a];
            if (visited[a]) continue;
            while (a < res.back() && m[res.back()]) {
                visited[res.back()] = 0;
                res.pop_back();
            }
            res += a;
            visited[a] = 1;
        }
        return res.substr(1);
    }
};

本文转自博客园Grandyang的博客,原文链接:移除重复字母[LeetCode] Remove Duplicate Letters ,如需转载请自行联系原博主。

相关文章
|
2月前
|
存储 算法
LeetCode第49题字母异位词分组
LeetCode第49题"字母异位词分组"的解题方法,通过将每个字符串的字符排序后作为键存储在HashMap中,有效地将所有字母异位词分组。
LeetCode第49题字母异位词分组
|
13天前
|
存储
Leetcode第49题(字母异位词分组)
LeetCode第49题要求将字符串数组中的字母异位词分组,可以通过将每个字符串排序后作为键存入哈希表,最后将哈希表中的值添加到结果列表中来实现。
11 1
|
13天前
|
算法
Leetcode第十七题(电话号码的字母组合)
这篇文章介绍了如何使用深度优先搜索(DFS)算法来解决LeetCode第17题——电话号码的字母组合问题,通过递归方法生成所有可能的字母组合。
12 0
Leetcode第十七题(电话号码的字母组合)
|
13天前
|
索引
【LeetCode 11】242.有效的字母异位词
【LeetCode 11】242.有效的字母异位词
11 0
【LeetCode 11】242.有效的字母异位词
|
12天前
|
算法
【LeetCode 52】17.电话号码的字母组合
【LeetCode 52】17.电话号码的字母组合
22 0
|
2月前
|
算法
LeetCode第17题电话号码的字母组合
该文章介绍了 LeetCode 第 17 题电话号码的字母组合的解法,通过分析得出可使用递归和回溯的思想解决,避免循环穷举的高循环次数,并给出了具体的编码实现,同时总结了该题较难理解,需要了解递归的本质,当嵌套循环层次多时可考虑递归。
LeetCode第17题电话号码的字母组合
|
4月前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
4月前
|
存储 算法 安全
LeetCode 题目 49:字母异位词分组 5种算法实现与典型应用案例【python】
LeetCode 题目 49:字母异位词分组 5种算法实现与典型应用案例【python】
|
4月前
|
存储
力扣经典150题第四十二题:字母异位词分组
力扣经典150题第四十二题:字母异位词分组
29 0
|
4月前
|
存储
力扣经典150题第四十一题:有效的字母异位词
力扣经典150题第四十一题:有效的字母异位词
22 0