0

文字列からすべての重複を削除し、可能な限り辞書編集的に最小の文字列を選択します。たとえば、文字列 cbacdcbc は adcb ではなく acdb を返します。

したがって、辞書編集的に最小の文字列を選択する必要がない場合、これは比較的単純な解決策になりますが、その事実を考慮すると、効率的な解決策にたどり着く方法がわかりません。これが私がこれまでに持っているものです：

    string removeDuplicateLetters(string s)
    {
        vector<bool> v(26,0);
        for(int i = 0; i < s.size(); i++) {
            v[s[i]-'a'] = 1;
        }

        string ss = "";
        for(int i = 0; i < s.size(); i++) {
            if(v[s[i]-'a']) {
                ss += s[i];
                v[s[i]-'a'] = 0;
            }
        }

        return ss;
    }
4

4 に答える 4

0

このアプローチは簡単だと思います。

まず、各文字の数を見つけます。

入力: s

vector<int> cnt(26);
int n=s.size();
for(int i=0;i<n;i++) cnt[s[i]-'a']++;

訪問したベクトルを持っている、vector<bool> visit(26);

string ans="";
for(int i=0;i<n;i++){
    int t=s[i]-'a';
    cnt[t]--;
    if(visit[t]) continue;
    while(ans.size()>0 && s[i]<ans.back() && cnt[ans.back()-'a']>0){
        visit[ans.back()-'a']=false;
        ans.pop_back();
    }
    ans.push_back(s[i]);
    visit[t]=true;
}
return ans;

時間計算量は O(n)

于 2019-06-27T09:57:58.927 に答える