首页 > 其他 > 详细

316. Remove Duplicate Letters (accumulate -> count of the difference elements in a vector)

时间:2018-12-31 20:46:20      阅读:215      评论:0      收藏: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 1:

Input: "bcabc"
Output: "abc"

Example 2:

Input: "cbacdcbc"
Output: "acdb"

 

Approach #1: C++. [brute froce]

class Solution {
public:
    string removeDuplicateLetters(string s) {
        int size = s.size();
        if (size == 0) return "";
        
        int l = 0;
        string ret = "";
        
        vector<int> cnt(26, 0);
        for (int j = 0; j < size; ++j) {
            cnt[s[j] - ‘a‘] = 1;
        }
        int total_diff = std::accumulate(cnt.begin(), cnt.end(), 0);
        
        for (int z = 0; z < total_diff; ++z) {
            for (int i = 0; i < 26; ++i) {
                int appear = -1;
                for (int j = l; j < size; ++j) {
                    if (s[j] - ‘a‘ == i && ret.find(‘a‘ + i) == -1) {
                        appear = j;
                        break;
                    }
                }
                if (appear == -1) continue;
                
                vector<int> cnt2(26, 0);
                for (int j = appear; j < size; ++j) 
                    cnt2[s[j] - ‘a‘] = 1;
                for (auto c : ret) 
                    cnt2[c - ‘a‘] = 1;
                int num = std::accumulate(cnt2.begin(), cnt2.end(), 0);
                if (num == total_diff) {
                    ret += char(‘a‘ + i);
                    l = appear + 1;
                    break;
                }
            }
        }
        
        return ret;
    }
};

  

Approach #2: C++.

class Solution {
public:
    string removeDuplicateLetters(string s) {
        vector<int> cand(256, 0);
        vector<bool> visited(256, false);
        
        for (auto c : s)
            cand[c]++;
        
        string ret = "0";
        
        for (auto c : s) {
            cand[c]--;
            if (visited[c]) continue;
            while (c < ret.back() && cand[ret.back()]) {
                visited[ret.back()] = false;
                ret.pop_back();
            }
            visited[c] = true;
            ret += c;
        }
        
        return ret.substr(1);
    }
};

  

reference:

https://leetcode.com/problems/remove-duplicate-letters/discuss/76767/C%2B%2B-simple-solution-easy-understanding

 

316. Remove Duplicate Letters (accumulate -> count of the difference elements in a vector)

原文:https://www.cnblogs.com/ruruozhenhao/p/10203221.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!