Chương trình tạo tất cả các chuỗi có thể bằng cách chọn các lựa chọn trong Python

Mô tả bài toán

Cho một chuỗi s bao gồm các ký tự chữ cái thường và các ký tự đặc biệt [, |, ]. Cú pháp [a|b|c] biểu thị rằng có thể chọn một trong các ký tự a, b hoặc c tại vị trí đó. Nhiệm vụ là tìm danh sách tất cả các chuỗi có thể mà s biểu diễn. Các cặp ngoặc vuông [] không được lồng nhau và có thể chứa bất kỳ số lượng lựa chọn nào.

Ví dụ: với đầu vào s = "[d|t|l]im[e|s]", đầu ra sẽ là ['dime', 'dims', 'lime', 'lims', 'time', 'tims'].

Giải thuật

1. Nếu chuỗi s rỗng, trả về danh sách chứa chuỗi rỗng.
2. Gán n là độ dài của s.
3. Khởi tạo hai danh sách: seq (để lưu các phần tử đang xây dựng) và res (kết quả).
4. Định nghĩa hàm đệ quy helper(pos):
   • Nếu pos == n: nối các phần tử trong seq và thêm vào res.
   • Ngược lại:
     • Nếu tìm thấy [ trong chuỗi con s[pos:]:
       • Xác định vị trí start (vị trí của [) và end (vị trí của ]) trong chuỗi gốc.
       • Với mỗi lựa chọn option trong chuỗi con giữa start và end tách bởi |:
         • Thêm đoạn cố định s[pos:start] và option vào seq.
         • Gọi đệ quy helper(end + 1).
         • Xóa hai phần tử vừa thêm khỏi seq (backtrack).
     • Nếu không tìm thấy [:
       • Thêm toàn bộ phần còn lại s[pos:] vào seq.
       • Gọi helper(n).
       • Xóa phần tử vừa thêm khỏi seq.
5. Từ hàm chính, gọi helper(0).
6. Trả về res đã sắp xếp theo thứ tự từ điển.

Ví dụ mã Python

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))

Đầu vào

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

Đầu ra

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