Chương trình tìm chia một chuỗi thành số chuỗi con duy nhất tối đa trong Python

Giả sử chúng ta có một chuỗi s, chúng ta phải tìm số chuỗi con duy nhất tối đa mà chuỗi đã cho có thể được tách thành. Chúng ta có thể chia chuỗi s thành bất kỳ danh sách chuỗi con không trống nào sao cho việc nối các chuỗi con tạo thành chuỗi ban đầu. Nhưng chúng ta phải tách các chuỗi con sao cho tất cả chúng đều giống nhau.

Vì vậy, nếu đầu vào là s =​​"pqpqrrr", thì đầu ra sẽ là 5 vì chúng ta có thể chia nó như ['p', 'q', 'pq', 'r', 'rr']. Nếu chúng ta chia như ['p', 'q', 'p', 'q', 'r', 'rr'] là không hợp lệ vì ở đây 'p' và 'q' hiện diện nhiều lần.

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

• res:=danh sách chỉ có một phần tử 0
• Định nghĩa một hàm dfs (). Điều này sẽ lấy s, đường dẫn là một tập hợp trống mới
• nếu s trống, thì
  • res [0]:=tối đa res [0] và kích thước của đường dẫn
  • trở lại
• đối với tôi trong phạm vi từ 1 đến cỡ s, thực hiện
  • x:=mảng con của s [từ chỉ mục 0 đến i-1]
  • nếu x không có trong đường dẫn, thì
    • dfs (chuỗi con của s [từ chỉ mục i đến cuối], đường dẫn U {x})
• Từ phương thức chính, hãy làm như sau -
• (các) dfs
• trả lại res [0]

Ví dụ

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

def solve(s):
   res = [0]
   def dfs(s, path=set()):
      if not s:
         res[0] = max(res[0], len(path))
         return
      for i in range(1, len(s)+1):
         x = s[:i]
         if x not in path:
            dfs(s[i:], path|{x})
   dfs(s)
   return res[0]
s = "pqpqrrr"
print(solve(s))

Đầu vào

"pqpqrrr"

Đầu ra

5