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 [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"