Word Break

Bài toán

Cho chuỗi s và một từ điển wordDict. Kiểm tra xem s có thể được ghép từ một hoặc nhiều từ trong wordDict hay không.

Ví dụ:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

Phân Tích & Tiếp Cận

Dynamic Programming

Gọi dp[i] là boolean, cho biết chuỗi con s[0...i-1] (độ dài i) có thể được tách thành công hay không. Mục tiêu: Tìm dp[s.length].

Công thức chuyển trạng thái: dp[i] = true NẾU tồn tại một điểm cắt j (0 <= j < i) sao cho:

1. dp[j] === true (Phần đầu s[0...j] đã tách được).
2. s[j...i] nằm trong wordDict (Phần đuôi là một từ hợp lệ).

Base case: dp[0] = true (Chuỗi rỗng luôn đúng).

function wordBreak(s: string, wordDict: string[]): boolean {
    const dp = new Array(s.length + 1).fill(false);
    dp[0] = true;

    const wordSet = new Set(wordDict); // Tìm kiếm O(1)

    for (let i = 1; i <= s.length; i++) {
        // Thử các điểm cắt j
        for (let j = 0; j < i; j++) {
            if (dp[j] && wordSet.has(s.substring(j, i))) {
                dp[i] = true;
                break; // Tìm thấy 1 cách là đủ
            }
        }
    }

    return dp[s.length];
}

• Time Complexity: $O(n^2)$.
• Space Complexity: $O(n)$.

Pattern Nhận Diện

Bài toán chia chuỗi (String Partitioning) thường dùng DP 1 chiều. Các biến thể:

• Word Break II (In ra tất cả các cách tách) -> Dùng Backtracking + Memoization.