Python中不同字符的最小子序列

2023-11-16 09:13:55

假设我们有一个文本,我们必须找到该文本在字典上最小的子序列,该子序列仅包含一次所有文本的不同字符。因此,如果输入类似于“ 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"
    • 作者:
    • 原文链接:
      更新时间:2023-11-16 09:13:55