Given a string s
, 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.
Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/
Example 1:
Input: s = "cdadabcc" Output: "adbc"
Example 2:
Input: s = "abcd" Output: "abcd"
Example 3:
Input: s = "ecbacba" Output: "eacb"
Example 4:
Input: s = "leetcode" Output: "letcod"
Constraints:
1 <= s.length <= 104
s
consists of lowercase English letters.
就是每次从后往前数,知道全部发现string里的字符,然后在该位置i之前的字符里找到最小的char。
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 40 41 42 | class Solution { public: string removeDuplicateLetters(string s) { int flag = 0; for(char ch : s){ flag |= 1<<(ch-'a'); } return helper(s,0, flag); } private: // count backward, until we find all chars, then find all string helper(string s, int start, int flag){// flag[i] == 0, means i+'a' need to be found if (start >= s.length() || flag ==0){ // stop condition return ""; } int newFlag = 0; int i = s.size()-1; for( ; i>=start;i--){ int mask = 1<<(s[i] -'a'); if(mask & flag){// if exist newFlag |= mask; } if(newFlag == flag){ break; } } // find the minChar; char minChar = s[i]; int minIndex = i; for (int j = i-1; j >=start; j--) { int mask = 1<<(s[j] - 'a'); if(mask&flag){ if(s[j] <= minChar){ minChar = s[j]; minIndex = j; } } } flag -= 1<< (minChar - 'a'); return string(1,minChar)+helper(s,minIndex+1,flag); } }; |
Mistakes:
1: helper() 里没有做stop condition 检测。
而且后来也没有做flag ==0 的检测
2:Line 30, 应该是从后向前检测的。 然而我写成从前向后了。 该死
3:同样的, line 33 ,应该有等号。
4: line 6, 第一遍写错了。写成了加号。 该死
***************第二遍的时候, 用了记录所有的位置 。然后每次寻找左右发生的最后一个位置。 并在所有char的最先一个位置。*****然而,速度才超过了22%.上面的超过97%
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 40 41 | class Solution { public: string removeDuplicateLetters(string s) { unordered_map<char,vector<int>> M; for(int i =s.length()-1; i>=0; i--){ M[s[i]].push_back(i); } string res=""; while(not M.empty()){ //among the last appearance index of 'a'->'z', find the minIndex int minLastIndex = s.length()-1; for(char ch = 'a';ch<='z'; ch++){ if(M.find(ch) != M.end()){ minLastIndex = min(minLastIndex, M[ch].front()); } } // now among all values, if it is bool findMinChar=false; int deletedIndex = 0; for(char ch = 'a';ch<='z'; ch++){ if(M.find(ch) != M.end() ){ if(not findMinChar && ( M[ch].back() <= minLastIndex)){ res+= ch; deletedIndex = M[ch].back(); M.erase(ch); findMinChar = true; continue; } if(findMinChar ){ while((not M[ch].empty()) && M[ch].back()<deletedIndex){ M[ch].pop_back(); } if(M[ch].empty()) M.erase(ch); } } } } return res; } }; |
No comments:
Post a Comment