[LeetCode] 316. 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.

給定一個隻含有小寫字母的字元串，移除重複的字元，每種字元隻出現1次，傳回字元串是按字典順序中最小的組合。

解法：貪心算法Greedy，用1個HashMap或者數組統計出現的字元。然後再周遊一遍數組, 假設position = 0，每次找到字元比position的小就更新position，同時也更新count，當count[i] == 0的時候，這個字元就是我們要找的結果字元串裡的第一個字元。之後因為其他字元的count還都 > 1，繼續在s.substring(position + 1)的子串裡遞歸查找第二個字元，注意要在這個子串裡把第一個字元清除掉。

Java：

public class Solution {
    public String removeDuplicateLetters(String s) {
        if(s == null || s.length() == 0) {
            return s;
        }
        
        int[] count = new int[26];
        char[] res = new char[26];
        int len = s.length();
        for(int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++; 
        }
        
        int pos = 0;
        for(int i = 0; i < len; i++) {
            if(s.charAt(i) < s.charAt(pos)) {
                pos = i;
            }
            count[s.charAt(i) - 'a']--;     
            if(count[s.charAt(i) - 'a'] == 0) {         // found first minimum char
                break;
            }
        }
        
        String charToRemove = String.valueOf(s.charAt(pos));
        return charToRemove + removeDuplicateLetters(s.substring(pos + 1).replaceAll(charToRemove, ""));
    }
}　　
           

Python:

class Solution(object):
    def removeDuplicateLetters(self, s):
        """
        :type s: str
        :rtype: str
        """
        remaining = collections.defaultdict(int)
        for c in s:
            remaining[c] += 1

        in_stack, stk = set(), []
        for c in s:
            if c not in in_stack:
                while stk and stk[-1] > c and remaining[stk[-1]]:
                    in_stack.remove(stk.pop())
                stk += c
                in_stack.add(c)
            remaining[c] -= 1
        return "".join(stk)　　
           

C++：

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);
    }
};　
           

All LeetCode Questions List 題目彙總

轉載于:https://www.cnblogs.com/lightwindy/p/8564419.html