Giả sử chúng ta có một danh sách các từ chuỗi. Chúng ta phải tạo một chuỗi được xây dựng bằng cách nối một dãy con của các từ sao cho mỗi chữ cái là duy nhất. Cuối cùng chúng ta phải tìm độ dài của đoạn nối dài nhất như vậy.
Vì vậy, nếu đầu vào giống như words =["xyz", "xyw", "wab", "cde"], thì đầu ra sẽ là 9, vì chúng tôi không thể chọn bất kỳ từ nào vì chúng chứa các ký tự trùng lặp.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau
ans:=0
Định nghĩa một hàm recom (). Điều này sẽ lấy i:=0, cur:=blank string
if i is same as size of words , then ans := maximum of ans and size of cur return recur(i + 1, cur) if all characters in words[i] are unique and all characters in (cur + words[i]) are unique, then recur(i + 1, cur + words[i]) From the main method do the following: recur() return ans
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, words): ans = 0 def is_all_unique(s): return len(set(s)) == len(s) def recur(i=0, cur=""): nonlocal ans if i == len(words): ans = max(ans, len(cur)) return recur(i + 1, cur) if is_all_unique(words[i]) and is_all_unique(cur + words[i]): recur(i + 1, cur + words[i]) recur() return ans ob = Solution() words = ["xyz", "xyw", "wab", "cde"] print(ob.solve(words))
Đầu vào
["xyz", "xyw", "wab", "cde"]
Đầu ra
9