LeetCode: 316. Remove Duplicate Letters

发表于 | 分类于

题目描述

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

Example 1:

1
2
Input: "bcabc"
Output: "abc"

Example 2:

1
2
Input: "cbacdcbc"
Output: "acdb"

原本还在想有没有什么更巧妙的方法，最后失败了hhh，果然是一个hard题

所以这道题目还是采取一种类似暴力搜索的方法，以题目的某个case "bbcaac"为例。

我的做法是使用了result来存储结果，一开始为一个空的字符串，每次决定一个字符的位置之后，讲字符加到result之后；另外我们用map来存储信息，map保存了所有没有被放入result中的字符，其中键为字符，value为一个vector<int>，它存放了所有字符出现的位置（index）。

上述例子的具体存放方式如下：

我的解的核心思想是，一个字符x如果能从map的key中放入result的结尾，那么map的剩下的所有key都至少有一个值在map[x][0]之后。因为map存放的是所有没有纳入result的字符，如果这些字符在map中对应的值里没有比map[x][0]大的，说明这些字符都排在x之前，那么它们应该早就放到result中了。

这个从map.begin()的iterator开始遍历（由于是使用STL的map进行存储，map的实现是一个红黑树，其保存了key的相对位置信息，所以可以用iterator实现lexicographical），看每个值（vector）的第一个元素，比如$’a’$的第一个元素就是3，说明第一个a出现在3的位置。这个时候，就需要检查其他所有的iterator的最后一个元素，如果说某个元素的最后一个值小于了3（比如b），就说明它在字符串中，所有的b都在3之前就出现了，a之后并没有b，但是，由于map存储的是所有没有在result中的结果，所以b还没有被放到result中去，可是a之后又没有b了，这样就造成了矛盾，说明a目前不能放到result里。

接着来看b。map['b'][0]为0，说明第一个b出现在0处，此时是成立的，因为map['a']和map['c']中都有在0之后的值，说明a和c都至少有一个在0处的b的后面，所以就把b放入result，并且把b这个key从map中删除。

接着，重新开始遍历字典，从a开始。现在3位置的a可以放入，因为map只剩下c了，c可以在a的后面，所以把a从map的key中取出，放入result。最后只剩下c了，就把c从map的key中取出，放入result。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    string removeDuplicateLetters(string s) {
        map<char, vector<int>> indexMap;
        string result = "";
        for (int i = 0; i<s.length(); i++){
            if (indexMap.find(s[i]) == indexMap.end()) {
                indexMap[s[i]] = {i};
            } else {
                indexMap[s[i]].push_back(i);
            }
        }
        while (!indexMap.empty()) {
            for (auto it = indexMap.begin(); it != indexMap.end();){
                bool isValid = true;
                for (auto it2 = indexMap.begin(); it2 != indexMap.end(); it2++) {
                    if (it->first == it2->first) {
                        continue;
                    }
                    if (it2->second[it2->second.size()-1] < it->second[0]) {
                        isValid = false;
                    }
                }
                if (isValid) {
                    result += it->first;
                    for (auto it2 = indexMap.begin(); it2 != indexMap.end(); it2++) {
                        while (it2->second[0] < it->second[0])
                            it2->second.erase(it2->second.begin());
                    }
                    indexMap.erase(it);
                    it = indexMap.begin();
                } else {
                    it++;
                }
            }
        }
        return result;
    }
};