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

Giả sử chúng ta có một chuỗi s gồm các ký tự chữ cái viết thường, các ký tự khác như "[", "|" và "]". Ở đây "[a | b | c]" cho biết "a", "b", hoặc "c" có thể được chọn là một khả năng. Chúng ta phải tìm một danh sách các chuỗi chứa tất cả các giá trị có thể có mà s có thể biểu diễn. Ở đây "[]" không thể được lồng vào nhau và có thể có bất kỳ số lượng lựa chọn nào.

Vì vậy, nếu đầu vào là s =​​"[d | t | l] im [e | s]", thì đầu ra sẽ là ['dime', 'dims', 'vôi', 'lims', 'time' , 'tims']

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

• nếu s trống, thì
  • trả về một danh sách với chuỗi trống
• n:=kích thước của s
• seq:=một danh sách mới, res:=một danh sách mới
• Xác định một hàm trợ giúp (). Điều này sẽ có vị trí
  • nếu pos giống n, thì
    • nối từng phần tử có trong seq và chèn vào res
  • nếu không,
    • if "[" trong chuỗi con của s [từ vị trí chỉ mục đến cuối], thì
      • start:=pos + index của "[" trong chuỗi con của s [từ index pos đến end]
      • end:=pos + index of "]" trong chuỗi con của s [từ index pos đến end]
      • đối với mỗi tùy chọn trong chuỗi con của s từ đầu đến cuối được phân tách bằng "|", hãy thực hiện
        • chèn s [từ vị trí chỉ mục đến đầu - 1] vào cuối seq
        • chèn tùy chọn vào cuối seq
        • người trợ giúp (end + 1)
        • xóa hai phần tử cuối cùng khỏi seq
  • nếu không,
    • chèn s [từ vị trí chỉ mục đến cuối] vào cuối seq
    • helper (n)
    • xóa phần tử cuối cùng khỏi seq
• Từ phương thức chính, hãy làm như sau:
• người trợ giúp (0)
• trả lại res theo thứ tự đã sắp xếp

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

Ví dụ

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

Đầu vào

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

Đầu ra

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