สมมติว่าเรามีรายการคำสตริง เราต้องสร้างสตริงที่สร้างขึ้นโดยการต่อคำที่ต่อเนื่องกันเพื่อให้แต่ละตัวอักษรไม่ซ้ำกัน ในที่สุดเราก็ต้องหาความยาวของการต่อกันที่ยาวที่สุด
ดังนั้น หากอินพุตเป็นเหมือนคำ =["xyz", "xyw", "wab", "cde"] ผลลัพธ์จะเป็น 9 เนื่องจากเราไม่สามารถเลือกคำใดๆ ได้เนื่องจากมีอักขระที่ซ้ำกัน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้
ตอบ :=0
กำหนดฟังก์ชัน recur() นี่จะใช้เวลา i:=0, cur:=สตริงว่าง
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
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
ตัวอย่าง
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))
อินพุต
["xyz", "xyw", "wab", "cde"]
ผลลัพธ์
9
