Chương trình kiểm tra chuỗi có thể tách thành từ trong danh sách cho trước trong Python

Cho danh sách từ words và chuỗi s không có dấu cách. Kiểm tra có thể tách s thành các từ trong danh sách không.

Ví dụ: words=["love","python","we","programming","language"], s="welovepythonprogramming" → True.

Thuật toán Backtracking + Memoization (Word Break):

• Chuyển words thành set để lookup O(1)
• Hàm đệ quy rec(i): có thể tách s[i:] không?
• Base case: i == len(s) → True
• Duyệt j từ i đến len(s)-1:
  • acc += s[j] (xây dựng substring s[i:j+1])
  • Nếu acc in words và rec(j+1) → True
• Return False

Triển khai

class Solution:
    def solve(self, words, s):
        words = set(words)
        
        def rec(i=0):
            if i == len(s):
                return True
            acc = ""
            for j in range(i, len(s)):
                acc += s[j]
                if acc in words:
                    if rec(j + 1):
                        return True
            return False
        
        return rec()

ob = Solution()
words = ["love", "python", "we", "programming", "language"]
s = "welovepythonprogramming"
print(ob.solve(words, s))

Đầu vào

["love", "python", "we", "programming", "language"], "welovepythonprogramming"

Đầu ra

True

Vấn đề hiệu suất: Code đệ quy không memoization → O(2^n) worst case (ví dụ s="aaaaaaaaab", words=["a","aa","aaa",...]). Cần thêm @lru_cache(None) cho rec hoặc DP bottom-up.

DP Bottom-up O(n²):

def wordBreak(s, wordDict):
    word_set = set(wordDict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    return dp[n]