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

pythonserver side programmingprogramming更新于 2025/8/25 7:08:17

假设我们有一个文本,我们必须找到按字典顺序排列的最小文本子序列,该子序列包含文本的所有不同字符,且恰好一次。因此,如果输入为"cdadabcc",则输出为"adbc"。

为了解决这个问题,我们将遵循以下步骤 −

  • 定义一个堆栈 st、两个映射 last_o 和 considered,它们最初是空白的
  • for i in range length of text – 1 down to 0
    • if text[i] is not present in last_o −
      • last_o[text[i]] := i
      • considered[text[i]] := false
    • i := 0
    • 当 i < 文本长度
      • 如果堆栈没有元素
        • 将 text[i] 推入堆栈
        • considered[text[i]] := true
        • 将 i 增加 1
      • 否则堆栈顶部 > text[i] 且 considered[text[i]] 为 false
        • 如果 last_o[stack top] > i
          • considered[stack top element] := false
          • 从堆栈弹出
        • 否则
          • considered[tex[i]] = true
          • 将 text[i] 插入堆栈
          • 将 i 增加 1
      • 否则,当堆栈顶部元素 < temp[i] 且 considered[text[i]] = false
        • 将 text[i] 插入堆栈
        • considered[text[i]] := true
        • 将 i 增加 1
      • 否则将 i 增加 1
  • 以相反的顺序返回堆栈的所有元素作为字符串

让我们看看下面的实现以便更好地理解 −

示例

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"

相关文章


有用资源