Tách Chuỗi Thực Chất Là Bài Toán Reachability Trên DP: Giải Word Break

"leetcode" -> có thể tách thành các từ trong từ điển không? Hai giây nhìn và câu trả lời hiển nhiên: "leet" + "code". Nhưng viết một hàm trả lời câu hỏi đó cho bất kỳ chuỗi và từ điển nào thì approach ngây thơ sụp đổ gần như ngay lập tức.

Điểm mấu chốt — cái làm cho Word Break trở thành bài DP chứ không phải bài string puzzle — là bạn không tìm kiếm một phân tách toàn cục. Bạn đang hỏi một câu hỏi reachability cục bộ tại mỗi chỉ số: liệu tôi có thể đến vị trí i bằng cách dùng các từ hợp lệ không? Khi đã framing như vậy, ba approach tự nhiên xuất hiện theo thứ tự độ phức tạp tăng dần.

Điều ràng buộc ép buộc gì

s.length <= 300, wordDict.length <= 1000, wordDict[i].length <= 20. Nhìn vào những con số đó một chút.

Giới hạn độ dài từ là 20 quan trọng. Nghĩa là tại mỗi vị trí i, bạn chỉ cần nhìn lại tối đa 20 ký tự để tìm từ có thể kết thúc ở đây — không cần nhìn ngược về tận vị trí 0. Giới hạn đó làm cho O(n^2) DP trở nên rất thoải mái. Ngay cả với n = 300, vòng lặp trong duyệt tối đa 300 × 300 = 90.000 cặp, mỗi lần tra cứu substring trong hash set là O(word_length) tối đa 20. Tổng công việc là hữu hạn và hoàn toàn xử lý được.

Brute-force O(2^n) là câu chuyện khác. Với n = 300, con số đó có 90 chữ số. Bạn không đợi được cái đó chạy xong.

Brute-force recursion

Cách đọc trực tiếp nhất: đứng tại chỉ số start, thử từng từ trong từ điển, xem có khớp với chuỗi bắt đầu từ đây không, và nếu có thì đệ quy trên phần còn lại.

class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        def backtrack(start: int) -> bool:
            if start == len(s):
                return True
            for word in wordDict:
                if s[start:].startswith(word):
                    if backtrack(start + len(word)):
                        return True
            return False
 
        return backtrack(0)

public class Solution {
    public bool WordBreak(string s, IList<string> wordDict) {
        return Backtrack(s, wordDict, 0);
    }
 
    private bool Backtrack(string s, IList<string> wordDict, int start) {
        if (start == s.Length) return true;
        foreach (string word in wordDict) {
            if (start + word.Length <= s.Length &&
                s.Substring(start, word.Length) == word) {
                if (Backtrack(s, wordDict, start + word.Length))
                    return true;
            }
        }
        return false;
    }
}

Code này chạy đúng với input nhỏ. Vấn đề là backtrack(start) có thể được gọi từ nhiều frame cha khác nhau — mỗi lần một word-prefix hợp lệ kết thúc tại cùng vị trí. Với s = "aaaa..." và wordDict = ["a", "aa", "aaa"], cây đệ quy bùng nổ theo cấp số nhân. Cùng một bài toán con, tính đi tính lại nhiều lần.

Time: O(2^n) trong worst case. Space: O(n) độ sâu call stack.

Memoization: loại bỏ công việc lặp lại

Cấu trúc đệ quy đúng; các bài toán con lặp mới sai. Fix là caching: một khi đã xác định backtrack(i) là True hay False, lưu kết quả lại và trả về ngay lần tiếp theo.

class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        word_set = set(wordDict)
        memo: dict[int, bool] = {}
 
        def dfs(start: int) -> bool:
            if start in memo:
                return memo[start]
            if start == len(s):
                return True
            for word in word_set:
                if s[start:start + len(word)] == word:
                    if dfs(start + len(word)):
                        memo[start] = True
                        return True
            memo[start] = False
            return False
 
        return dfs(0)

public class Solution {
    private Dictionary<int, bool> _memo = new();
 
    public bool WordBreak(string s, IList<string> wordDict) {
        _memo.Clear();
        var wordSet = new HashSet<string>(wordDict);
        return Dfs(s, wordSet, 0);
    }
 
    private bool Dfs(string s, HashSet<string> wordSet, int start) {
        if (_memo.TryGetValue(start, out bool cached)) return cached;
        if (start == s.Length) return true;
        foreach (string word in wordSet) {
            if (start + word.Length <= s.Length &&
                s.Substring(start, word.Length) == word) {
                if (Dfs(s, wordSet, start + word.Length)) {
                    _memo[start] = true;
                    return true;
                }
            }
        }
        _memo[start] = false;
        return false;
    }
}

Việc chuyển wordDict sang word_set quan trọng ở đây. Dù iterate qua set để kiểm tra từng từ vẫn là O(|wordDict|) mỗi lần gọi, nhưng một khi mỗi chỉ số start chỉ được tính đúng một lần, tổng số bài toán con là n và mỗi bài làm O(|wordDict| × max_word_len) công việc.

Time: O(n × W × L). Space: O(n) cho memo, cộng O(n) call stack.

Call stack là điều tôi sẽ đánh dấu trong production. Với n = 300 và từ điển chỉ toàn ký tự đơn khớp, độ sâu đệ quy có thể chạm 300. Giới hạn mặc định của Python là 1000, nên vẫn sống được — nhưng con số đó khiến tôi không thoải mái. Trong trường hợp pathological bạn cần sys.setrecursionlimit và các stack frame tốn thêm bộ nhớ mà phiên bản bottom-up tránh được hoàn toàn.

Bottom-up tabulation: phiên bản tôi sẽ ship

Đảo chiều. Thay vì hỏi "từ đây tôi có đến được cuối không?", hỏi "vị trí i có reachable từ bất kỳ vị trí hợp lệ nào trước đó không?". Định nghĩa dp[i] là True nếu prefix s[0:i] có thể được tách thành các từ trong từ điển.

Base case: dp[0] = True. Prefix rỗng cần không có từ nào và luôn hợp lệ.

Transition: dp[i] = True nếu tồn tại j < i sao cho dp[j] = True và s[j:i] nằm trong word set.

s = "leetcode", wordDict = {"leet", "code"}

dp = [T, F, F, F, F, F, F, F, F]
      0  1  2  3  4  5  6  7  8

i=1: j=0 -> dp[0]=T, s[0:1]="l"? Không.  dp[1]=F
i=2: j=0 -> "le"? Không. j=1 -> dp[1]=F, bỏ qua.  dp[2]=F
i=3: j=0 -> "lee"? Không. dp[3]=F
i=4: j=0 -> dp[0]=T, s[0:4]="leet"? CÓ -> dp[4]=T
i=5: j=0 -> "leetc"? Không. j=4 -> dp[4]=T, s[4:5]="c"? Không. dp[5]=F
i=6: j=4 -> dp[4]=T, s[4:6]="co"? Không. dp[6]=F
i=7: j=4 -> s[4:7]="cod"? Không. dp[7]=F
i=8: j=4 -> dp[4]=T, s[4:8]="code"? CÓ -> dp[8]=T

Kết quả: dp[8] = True

class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        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]

public class Solution {
    public bool WordBreak(string s, IList<string> wordDict) {
        var wordSet = new HashSet<string>(wordDict);
        int n = s.Length;
        bool[] dp = new bool[n + 1];
        dp[0] = true;
 
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordSet.Contains(s.Substring(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
 
        return dp[n];
    }
}

Không có call stack. Không có dictionary allocation mỗi frame. Mảng dp chỉ có 301 boolean. Footprint bộ nhớ rất nhỏ.

Time: O(n^2 × L) — vòng lặp trong trên j chạy tối đa n lần cho mỗi i, và mỗi lần tra cứu s[j:i] trong hash set cần hash substring trong O(i - j). Trong thực tế i - j hiếm khi đạt 300 vì giới hạn độ dài từ là 20. Space: O(n + W) cho mảng dp và word set.

Cạnh nét đứt cho thấy nếu "leetcode" là một từ đơn trong từ điển, dp[8] sẽ reachable trực tiếp từ dp[0] — thuật toán tìm ra ở vòng lặp j=0 khi i=8. Cạnh nét liền thể hiện con đường thực tế qua "leet" + "code".

Tối ưu vòng lặp trong khi độ dài từ có giới hạn

Vì wordDict[i].length <= 20, bạn có thể thay vòng lặp j từ 0 đến i bằng vòng từ max(0, i - 20) đến i. Ở n = 300 điều này hầu như không quan trọng, nhưng tốt để biết cái optimization này tồn tại cho những bài có chuỗi dài hơn nhiều. Cấu trúc giữ nguyên; constant factor cải thiện.

Edge cases

s không tách được (s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]): dp[7] trở thành True qua "cats"+"dog" (vị trí 0-4-7) nhưng dp[9] không bao giờ True vì "og" không có trong từ điển. Hàm trả về dp[9] = False. Việc tách được một phần không quan trọng — điều quan trọng là không có j nào thỏa mãn cả dp[j] = True lẫn s[j:9] trong word_set.

Tái sử dụng từ (s = "applepenapple", wordDict = ["apple", "pen"]): DP tìm dp[5] = True (apple), dp[8] = True (pen), dp[13] = True (apple lần hai). Cùng một từ xuất hiện hai lần trong chuỗi phân tách được xử lý tự động vì lookup là với một set không có bộ đếm sử dụng.

Từ dài hơn chuỗi (wordDict = ["toolong"], s = "short"): s.Substring(j, i - j) với i - j > s.Length - j được bảo vệ bởi vòng ngoài i <= n và điều kiện trong j < i, nên substring luôn hợp lệ. Từ "toolong" đơn giản không bao giờ khớp với bất kỳ lát cắt s[j:i] nào.

So sánh các approach

W = |wordDict|, L = độ dài từ tối đa, n = s.length.

Pattern reachability và những nơi nó xuất hiện tiếp theo

Word Break là bài boolean reachability được khoác áo bài string. Mental model — dp[i] là True nếu bất kỳ vị trí True trước đó j có một "bước nhảy" hợp lệ đến i — xuất hiện trong một nhóm bài mà cấu trúc giống hệt nhau khi bạn lột bỏ cái vỏ bề mặt.

LeetCode 140 (Word Break II) yêu cầu tất cả các chuỗi phân tách hợp lệ, không chỉ liệu có tồn tại hay không. Bảng dp trở thành cấu trúc backtracking — tại mỗi vị trí True bạn lưu những giá trị j nào đã kích hoạt nó, rồi tái tạo các đường đi. Logic reachability giống hệt; format output thay đổi.

LeetCode 472 (Concatenated Words) chạy Word Break như một subroutine: một từ trong danh sách là "concatenated" nếu nó có thể tách thành các từ khác từ cùng danh sách đó. Bạn chạy wordBreak trên từng candidate với các từ còn lại làm từ điển.

LeetCode 91 (Decode Ways) là biến thể đếm: dp[i] trở thành integer (số cách decode s[0:i]), bước nhảy là một hoặc hai ký tự (chữ số hợp lệ hoặc hai chữ số hợp lệ), và transition cộng thay vì OR. Cùng một bottom-up table, ngữ nghĩa khác.

LeetCode 132 (Palindrome Partitioning II) hỏi số lần cắt tối thiểu để chia chuỗi thành các palindrome. Kiểm tra "substring này có phải palindrome không" thay thế kiểm tra "substring này có trong từ điển không", và bảng lưu số lần cắt thay vì boolean. Cấu trúc bên ngoài giống hệt.

Bài coin change trong series này là cặp sinh đôi cấu trúc gần nhất: dp[amount] = True/min nếu bất kỳ dp[amount - coin] nào là True/finite. Cùng logic hop-from-previous-state. Điểm khác biệt duy nhất là Coin Change nhảy lùi theo mệnh giá đồng xu và Word Break nhảy lùi theo độ dài từ. Nếu nhận ra điểm đó, bạn sẽ nhận ra gia đình bài này ngay khi nhìn thấy.