leetcode 316. Remove Duplicate Letters 去除重复字符字典序最小字符串+贪心+递归

r囧r小猫 2022-06-07 01:08 155阅读 0赞

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”

就是去除重复的元素，但是要求所得到的字符串的字典序最小。

没想到应该怎么做，但是网上看到了一个很简洁的代码，思路就是贪心+递归。

首先是遍历递归统计每一个字符出现的次数，然后选择当前的最小的字符去做递归，代码很棒，不过我还有点想不清楚。

代码如下：

/*
     * https://discuss.leetcode.com/topic/31404/a-short-o-n-recursive-greedy-solution
     * 贪心算法
     * */
    public class Solution {
       public String removeDuplicateLetters(String s) 
       {
           if(s==null || s.length()<=0)
               return "";
           else 
           {
               int[] count=new int[26];
               for(int i=0;i<s.length();i++)
                   count[s.charAt(i)-'a']++;
               int pos=0;
               for(int i=0;i<s.length();i++)
               {
                   if(s.charAt(i)<s.charAt(pos))
                       pos=i;
                   count[s.charAt(i)-'a']--;
                   if(count[s.charAt(i)-'a']==0)
                       break;
               }
               //System.out.println(s.charAt(pos)+"     "+s.substring(pos+1).replace(""+s.charAt(pos),""));
               String res = s.charAt(pos)+ removeDuplicateLetters(s.substring(pos+1).replace(""+s.charAt(pos),""));
               return res;
           }
       }
    }

下面是C++的做法，说实话真的不喜欢C++的字符串替换函数，还是Java的好用，

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    
    class Solution
    {
    public:
        string removeDuplicateLetters(string s)
        {
            string res = "0";
            vector<int> count(256, 0), visit(256, 0);
            for (char c : s)
                count[c]++;
    
            for (char c : s)
            {
                count[c]--;
                if (visit[c] == 1)
                    continue;
                else 
                {
                    while (res.size() > 0 && count[res.back()] > 0 && res.back() > c)
                    {
                        visit[res.back()] = 0;
                        res.pop_back();
                    }
                    res += c;
                    visit[c] = 1;
                }
            }
    
            res = res.substr(1);
            return res;
        }
    
    
        string removeDuplicateLettersByDFS(string s)
        {
            if (s.length() <= 0)
                return s;
            else
            {
                vector<int> count(26, 0);
                for (char c : s)
                    count[c - 'a'] ++;
                int pos = 0;
                for (int i = 0; i < s.length(); i++)
                {
                    if (s[i] < s[pos])
                        pos = i;
                    count[s[i] - 'a']--;
                    if (count[s[i] - 'a'] == 0)
                        break;
                }
    
                string tar = "";
                tar += s[pos];
                string left = getRes(s.substr(pos + 1), tar);
                return tar + removeDuplicateLetters(left);
            }
        }
    
        string getRes(string s, string tar)
        {
            int pos = s.find(tar);
            while (pos != s.npos)
            {
                s = s.replace(pos, tar.length(), "");
                pos = s.find(tar);
            }
            return s;
        }
    };