ลำดับที่เล็กที่สุดของอักขระที่แตกต่างใน Python

สมมติว่าเรามีข้อความ เราต้องหาลำดับย่อยของข้อความที่เล็กที่สุดเกี่ยวกับพจนานุกรมศัพท์ซึ่งมีอักขระที่ชัดเจนทั้งหมดของข้อความในครั้งเดียว ดังนั้นหากอินพุตเป็นเหมือน “cdadabcc” เอาต์พุตจะเป็น “adbc”

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดสแต็ก st, สองแผนที่ last_o และถือว่าว่างในตอนแรก
• สำหรับ i ในความยาวของช่วงข้อความ – 1 down to 0
  • ถ้าไม่มีข้อความ[i] ใน last_o −
    • last_o[text[i]] :=i
    • ถือว่า[text[i]] :=false
  • ผม :=0
  • ในขณะที่ฉัน <ความยาวของข้อความ
    • ถ้า stack ไม่มีองค์ประกอบ
      • พุชข้อความ[i] ลงในสแต็ก
      • ถือว่า[text[i]] :=true
      • เพิ่ม i ขึ้น 1
    • มิฉะนั้น stack top> text[i] และพิจารณาว่า[text[i]] เป็นเท็จ
      • iflast_o[stack top]> i
        • ถือว่า[stack top element] :=false
        • ป๊อปจากสแต็ก
      • มิฉะนั้น
        • ถือว่า[tex[i]] =จริง
        • แทรก text[i] ลงในสแต็ก
        • เพิ่ม i ขึ้น 1
    • มิฉะนั้นเมื่อองค์ประกอบด้านบนสแต็ก
    • แทรก text[i] ลงในสแต็ก
    • ถือว่า[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"