假设我们有一个文本,我们必须找到该文本在字典上最小的子序列,该子序列仅包含一次所有文本的不同字符。因此,如果输入类似于“ 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 [stack top]> 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"