Python中不同字符的最小子序列
假设我们有一个文本，我们必须找到该文本在字典上最小的子序列，该子序列仅包含一次所有文本的不同字符。因此，如果输入类似于“cdadabcc”，那么输出将为“adbc”。
为了解决这个问题，我们将遵循以下步骤-
定义一个堆栈st，两个映射last_o并考虑，它们最初是空白的
对于我在文本范围内的长度–1降至0
如果堆栈没有元素
否则，栈顶>text[i]并认为[text[i]]为假
否则，当堆栈顶部元素<temp[i]并认为[text[i]]=false时
否则我加1
将text[i]推入堆栈
考虑[text[i]]：=true
使我增加1
认为[tex[i]]=true
将text[i]插入堆栈
使我增加1
考虑[堆栈顶部元素]：=假
从堆栈弹出
如果last_o[stacktop]>i
除此以外
将text[i]插入堆栈
考虑[text[i]]：=true
使我增加1
last_o[text[i]]：=i
考虑[text[i]]：=假
如果在last_o中没有text[i]-
i：=0
而我<文字长度
以相反的顺序将堆栈的所有元素作为字符串返回
让我们看下面的实现以更好地理解-
示例
class Solution(object):
def smallestSubsequence(self, text):
"""
:type text: str
:rtype: str
"""
stack = []
last_o = {}
considered = {}
for i in range(len(text)-1,-1,-1):
if text[i] not in last_o:
last_o[text[i]] = i
considered[text[i]] = False
print(last_o)
i = 0
while i < len(text):
print(stack,i,text[i])
if len(stack) == 0:
stack.append(text[i])
considered[text[i]] = True
i+=1
elif stack[-1]>text[i] and considered[text[i]] == False:
if last_o[stack[-1]]>i:
considered[stack[-1]]=False
stack.pop()
else:
considered[text[i]] = True
stack.append(text[i])
i+=1
elif stack[-1]<text[i] and considered[text[i]] == False:
stack.append(text[i])
considered[text[i]] = True
i+=1
else:
i+=1
return "".join(i for i in stack)输入值
"cdadabcc"
输出结果
"adbc"