โปรแกรมสร้างสตริงที่เป็นไปได้ทั้งหมดโดยใช้ตัวเลือกใน python

สมมติว่าเรามีสตริงของอักขระอักษรตัวพิมพ์เล็ก อักขระอื่นๆ เช่น "[", "|" และ "]" ที่นี่ "[a|b|c]" ระบุว่าสามารถเลือก "a", "b" หรือ "c" ได้ เราต้องหารายการสตริงที่มีค่าที่เป็นไปได้ทั้งหมดที่สามารถแสดงได้ ที่นี่ "[]" ไม่สามารถซ้อนและอาจมีตัวเลือกมากมาย

ดังนั้น หากอินพุตเป็น s ="[d|t|l]im[e|s]" ผลลัพธ์จะเป็น ['dime', 'dims', 'lime', 'lims', 'time' , 'ทิม']

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

• ถ้า s ว่าง ก็
  • ส่งคืนรายการด้วยสตริงว่าง
• n :=ขนาดของ s
• seq :=รายการใหม่ res :=รายการใหม่
• กำหนดฟังก์ชัน helper() นี่จะใช้เวลา pos
  • ถ้า pos เหมือนกับ n แล้ว
    • รวมแต่ละองค์ประกอบที่มีอยู่ใน seq และแทรกลงใน res
  • มิฉะนั้น
    • ถ้า "[" ในสตริงย่อยของ s[จากดัชนี pos ถึง end] แล้ว
      • start :=pos + index of "[" ในสตริงย่อยของ s[จาก index pos ถึง end]
      • สิ้นสุด :=pos + ดัชนีของ "]" ในสตริงย่อยของ s[จากดัชนี pos ถึงปลาย]
      • สำหรับแต่ละตัวเลือกในสตริงย่อยของ s ตั้งแต่ต้นจนจบแยกด้วย "|" ทำ
        • แทรก s[จากดัชนี pos to start - 1] ที่ส่วนท้ายของ seq
        • แทรกตัวเลือกที่ส่วนท้ายของ seq
        • ตัวช่วย(จบ + 1)
        • ลบสององค์ประกอบสุดท้ายออกจาก seq
  • มิฉะนั้น
    • แทรก s[จากดัชนี pos ถึง end] ที่ส่วนท้ายของ seq
    • ผู้ช่วย(n)
    • ลบองค์ประกอบสุดท้ายออกจาก seq
• จากวิธีหลัก ให้ทำดังนี้:
• ตัวช่วย(0)
• ส่งคืน res ตามลำดับการเรียงลำดับ

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

ตัวอย่าง

class Solution:
   def solve(self, s):
      if not s:
         return [""]
      n = len(s)

      def helper(pos):
         if pos == n:
            res.append("".join(seq))
         else:
            if "[" in s[pos:]:
               start = pos + s[pos:].index("[")
               end = pos + s[pos:].index("]")
               for option in s[start + 1 : end].split("|"):
                  seq.append(s[pos:start])
                  seq.append(option)
                  helper(end + 1)
                  seq.pop()
                  seq.pop()
            else:
               seq.append(s[pos:])
               helper(n)
               seq.pop()

         seq = []
         res = []
         helper(0)
         return sorted(res)

ob = Solution()
s = "[d|t|l]im[e|s]"
print(ob.solve(s))

อินพุต

"[d|t|l]im[e|s]"

ผลลัพธ์

['dime', 'dims', 'lime', 'lims', 'time', 'tims']