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

สมมติว่ามีสตริง s ที่ประกอบด้วยตัวอักษรภาษาอังกฤษพิมพ์เล็ก และอักขระพิเศษ เช่น [, |, และ ] โดยรูปแบบ [a|b|c] หมายถึงสามารถเลือกได้เพียงหนึ่งใน a, b, หรือ c เท่านั้น เราต้องการหารายการสตริงทั้งหมดที่ s สามารถแทนได้ โดย [] ไม่สามารถซ้อนกันได้ และอาจมีตัวเลือกได้ไม่จำกัดจำนวน

ตัวอย่างเช่น หากอินพุตคือ s = "[d|t|l]im[e|s]" ผลลัพธ์จะเป็น ['dime', 'dims', 'lime', 'lims', 'time', 'tims']

ขั้นตอนการแก้ปัญหา

1. ถ้า s ว่าง ให้คืนค่ารายการที่มีสตริงว่าง
2. กำหนด n = ความยาวของ s
3. สร้างรายการ seq และ res ว่างๆ
4. สร้างฟังก์ชัน helper(pos) ที่รับตำแหน่งปัจจุบัน:
   • ถ้า pos == n ให้รวมสมาชิกใน seq และเพิ่มลงใน res
   • มิฉะนั้น:
     • ถ้ามี [ ใน s[pos:]:
       • หาตำแหน่ง start และ end ของวงเล็บ
       • วนลูปแต่ละตัวเลือกใน s[start+1:end] ที่แบ่งด้วย |:
         • เพิ่ม s[pos:start] และตัวเลือกเข้า seq
         • เรียก helper(end + 1)
         • ลบ 2 ตัวสุดท้ายออกจาก seq (backtrack)
     • มิฉะนั้น (ไม่มีวงเล็บเหลือ):
       • เพิ่ม s[pos:] เข้า seq
       • เรียก helper(n)
       • ลบตัวสุดท้ายออกจาก seq
5. จากเมธอดหลัก เรียก helper(0) แล้วคืนค่า res ที่เรียงลำดับแล้ว

ตัวอย่างโค้ด

class Solution:
    def solve(self, s):
        if not s:
            return [""]
        n = len(s)
        seq = []
        res = []
        
        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()
        
        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']