Chuỗi ký tự khác biệt nhỏ nhất trong Python

Giả sử chúng ta có một văn bản, chúng ta phải tìm dãy con nhỏ nhất về mặt từ vựng của văn bản chứa tất cả các ký tự riêng biệt của văn bản đúng một lần. Vì vậy, nếu đầu vào giống như "cdadabcc", thì đầu ra sẽ là "adbc".

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một ngăn xếp, hai bản đồ last_o và được xem xét, ban đầu chúng trống
• cho tôi trong phạm vi độ dài của văn bản - 1 xuống 0
  • nếu văn bản [i] không có trong last_o -
    • last_o [text [i]]:=i
    • được coi là [text [i]]:=false
  • i:=0
  • while i <độ dài của văn bản
    • nếu ngăn xếp không có phần tử nào
      • đẩy văn bản [i] vào ngăn xếp
      • được coi là [text [i]]:=true
      • tăng tôi lên 1
    • nếu không thì ngăn xếp trên cùng> văn bản [i] và được coi là [văn bản [i]] là sai
      • if last_o [stack top]> i
        • được coi là [phần tử trên cùng của ngăn xếp]:=false
        • bật ra từ ngăn xếp
      • Mặt khác
        • coi [tex [i]] =true
        • chèn văn bản [i] vào ngăn xếp
        • tăng tôi lên 1
    • ngược lại khi phần tử trên cùng của ngăn xếp
    • chèn văn bản [i] vào ngăn xếp
    • được coi là [text [i]]:=true
    • tăng tôi lên 1
  • nếu không, hãy tăng tôi lên 1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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)

Đầu vào

"cdadabcc"

Đầu ra

"adbc"