Pattern · Quy hoạch động 1 chiềuTrung bình ~30 phút đọc + làm

Tách Chuỗi Thành TừWord Break

Hiểu bài

Cho chuỗi s và danh sách từ wordDict. Hỏi có thể tách s thành chuỗi các từ trong wordDict không? Từ có thể dùng nhiều lần.

Ví dụ:

s = "leetcode", wordDict = ["leet","code"]
output = true  // "leet" + "code"

s = "applepenapple", wordDict = ["apple","pen"]
output = true  // "apple" + "pen" + "apple"

s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
output = false  // không có cách tách hợp lệ

Cái bẫy: cắt tham lam theo từ khớp đầu tiên là sai.

Với "catsandog", cắt được "cat" rồi "sand" tưởng sắp xong, nhưng còn lại "og" — không từ nào khớp, mà giờ đã quá muộn để lùi lại chọn "cats".
Phải cân nhắc được mọi cách cắt mà vẫn không tính lại chồng chéo.

Cách cơ bảnO(2ⁿ) time — mỗi vị trí có thể tách hoặc không

// Đệ quy không memoization — kiểm tra mọi cách tách
function wordBreakNaive(s: string, wordDict: string[]): boolean {
  const wordSet = new Set(wordDict)

  function dfs(start: number): boolean {
    if (start === s.length) return true
    for (let end = start + 1; end <= s.length; end++) {
      const word = s.slice(start, end)
      if (wordSet.has(word) && dfs(end)) return true
    }
    return false
  }

  return dfs(0)
}

Vì sao cách này chậm:

Tính lại cùng subproblem từ nhiều nhánh khác nhau.

Thêm memoization (lưu kết quả dfs(i)) sẽ giảm xuống O(n²×m) — tương đương DP bottom-up.

Mở khoá để xem lời giải tối ưu, chạy thử từng bước và câu hỏi liên quan

Xem đầy đủ chạy thử từng bước, Big-O, trường hợp biên và biến thể công ty Việt Nam.

Mở khoá Pro Xem Lifetime

Hiểu bài

Cho chuỗi s và danh sách từ wordDict. Hỏi có thể tách s thành chuỗi các từ trong wordDict không? Từ có thể dùng nhiều lần.

Ví dụ:

s = "leetcode", wordDict = ["leet","code"]
output = true  // "leet" + "code"

s = "applepenapple", wordDict = ["apple","pen"]
output = true  // "apple" + "pen" + "apple"

s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
output = false  // không có cách tách hợp lệ

Cái bẫy: cắt tham lam theo từ khớp đầu tiên là sai.

Với "catsandog", cắt được "cat" rồi "sand" tưởng sắp xong, nhưng còn lại "og" — không từ nào khớp, mà giờ đã quá muộn để lùi lại chọn "cats".
Phải cân nhắc được mọi cách cắt mà vẫn không tính lại chồng chéo.

// Đệ quy không memoization — kiểm tra mọi cách tách function wordBreakNaive(s: string, wordDict: string[]): boolean { const wordSet = new Set(wordDict) function dfs(start: number): boolean { if (start === s.length) return true for (let end = start + 1; end <= s.length; end++) { const word = s.slice(start, end) if (wordSet.has(word) && dfs(end)) return true } return false } return dfs(0) }