首页 > 代码库 > leetcode 316. Remove Duplicate Letters
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"
题目意思：去掉重复的字符，保持元序列的位置，并使得字典序最小
真的是。。。想了半天也没想到用栈。看了他人的代码，还有用string 直接搞的
class Solution {public: string removeDuplicateLetters(string s) { int n = s.length(); vector<int> cnt(26); vector<int> vis(26); for (int i = 0; i < n; ++i) { int x = s[i] - ‘a‘; cnt[x]++; } stack<int> st; for (int i = 0; i < n; ++i) { int x = s[i] - ‘a‘; cnt[x]--; if (st.empty()) { st.push(x); vis[x] = 1; } else { while (!st.empty() && st.top() > x && cnt[st.top()] && !vis[x]) { vis[st.top()] = 0; st.pop(); } if (!vis[x]) st.push(x),vis[x] = 1; } } string t = ""; while (!st.empty()) { int y = st.top(); st.pop(); t = char(y + ‘a‘) + t; } return t; }};
class Solution {public: string removeDuplicateLetters(string s) { vector<int> dict(256, 0); vector<bool> visited(256, false); for(auto ch : s) dict[ch]++; string result = "0"; /** the key idea is to keep a monotically increasing sequence **/ for(auto c : s) { dict[c]--; /** to filter the previously visited elements **/ if(visited[c]) continue; while(c < result.back() && dict[result.back()]) { visited[result.back()] = false; result.pop_back(); } result += c; visited[c] = true; } return result.substr(1); }};
leetcode 316. Remove Duplicate Letters
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。