316 Remove Duplicate Letters
316. Remove Duplicate Letters
题目: https://leetcode.com/problems/remove-duplicate-letters/
难度:
Hard
思路
这道题让我们移除重复字母，使得每个字符只能出现一次，而且结果要按最优的字母顺序排列，前提是不能打乱其原本的相对位置。 - 先用remaining统计所有出现字母出现过的次数； - res就是输出结果的字母顺序(list)，最后用join连接起来作为返回值(str)； - 在stack(set)中的元素意味着其已经出现在最终结果中；
对s中每个字母c，首先看它在stack中有没有出现过： 1. 如果没有那么只要res最后一个字母的ASCII值大于c，且其剩余次数大于0，就将其在res和stack中删去，不停做此操作 2. 如果有了那么说明已经出现在最终结果中，只需要将其统计次数减去1以防后面挪动位置要做判断
做完这些后必须要把c加入到stack和res中去，代表c已经加入到最终结果中的目前应该处于的位置
参考python的colloections之defaultdict模块
class Solution(object):
def removeDuplicateLetters(self, s):
"""
:type s: str
:rtype: str
"""
remaining = collections.defaultdict(int)
for c in s:
remaining[c] += 1
res, stack = [], set()
for c in s:
if c not in stack:
while res and res[-1] > c and remaining[res[-1]] > 0:
stack.remove(res.pop())
res.append(c)
stack.add(c)
remaining[c] -= 1
return ''.join(res)
还有别的一些优美的解法，参考stefan的回答
递归贪心版本
class Solution(object):
def removeDuplicateLetters(self, s):
"""
:type s: str
:rtype: str
"""
for c in sorted(set(s)):
suffix = s[s.index(c):]
if set(suffix) == set(s):
return c + self.removeDuplicateLetters(suffix.replace(c, ''))
return ''
class Solution(object):
def removeDuplicateLetters(self, s):
"""
:type s: str
:rtype: str
"""
result = ''
while s:
i = min(map(s.rindex, set(s)))
c = min(s[:i+1])
result += c
s = s[s.index(c):].replace(c, '')
return result
class Solution(object):
def removeDuplicateLetters(self, s):
"""
:type s: str
:rtype: str
"""
rindex = {c: i for i, c in enumerate(s)}
result = ''
for i, c in enumerate(s):
if c not in result:
while c < result[-1:] and i < rindex[result[-1]]:
result = result[:-1]
result += c
return result
