- Tại sao tham lam (Greedy) bị sai?: Với chuỗi
s = "aaaaaa"(gồm \(6\) chữ'a') và từ điển{"aaaa", "aaa"}, nếu ưu tiên cắt từ dài nhất"aaaa"trước thì phần dư"aa"không khớp từ nào; trong khi cắt thành"aaa" + "aaa"lại thành công. - Tại sao quay lui thuần túy bị quá thời gian (TLE)?: Trên chuỗi
s = "aaaa...ab"và từ điển{"a", "aa", "aaa", ...}, cùng một vị trí hậu tốs[i..n-1]bị tính đi tính lại theo mọi cách viết \(i\) thành tổng có thứ tự của các độ dài từ (\(2^{i-1}\) cách), dẫn tới độ phức tạp \(O(2^n)\). - Định nghĩa trạng thái Quy hoạch động: Gọi
dp[i]là giá trị logic (true/false) cho biết tiền tố độ dài \(i\) của chuỗi (tứcs[0..i-1]) có tách được thành các từ trong từ điển hay không, với cơ sởdp[0] = true(chuỗi rỗng). - Công thức chuyển trạng thái tối ưu:
dp[i] = truenếu tồn tại điểm cắt cuối cùng \(j \in [\max(0, i - L_{\max}),\; i - 1]\) sao chodp[j] == truevà chuỗi cons[j..i-1]nằm trong tập băm từ điển (với \(L_{\max}\) là độ dài từ dài nhất trong từ điển).
Phản ví dụ đánh bại Tham lam và bẫy nổ tổ hợp O(2ⁿ)
Cho chuỗi không rỗng s có độ dài \(n\) và danh sách các từ wordDict. Hãy xác định xem s có thể được phân tách thành một hoặc nhiều từ nằm trong wordDict nối tiếp nhau hay không (một từ trong wordDict được phép sử dụng lại nhiều lần).
Khi gặp bài toán này trong phỏng vấn, có hai hướng tiếp cận ngây thơ mà bạn cần nhận diện ngay để giải thích với người phỏng vấn vì sao chúng không đạt yêu cầu:
-
Hướng tiếp cận Tham lam (khớp từ ngắn nhất hoặc dài nhất từ đầu chuỗi):
- Giả sử
s = "goalspecial"và từ điển là{"go", "goal", "goals", "special"}. - Nếu chọn từ ngắn nhất khớp đầu chuỗi là
"go", phần còn lại"alspecial"bị tắc hoàn toàn. - Nếu chọn từ dài nhất khớp đầu chuỗi là
"goals", phần còn lại"pecial"cũng bị tắc. - Đáp án đúng duy nhất phải dừng ở từ có độ dài lưng chừng là
"goal"để chừa lại"special". Như vậy, tại thời điểm đứng ở vị trí \(j\), ta không thể biết trước độ dài từ nào sẽ dẫn tới đích nếu không xét các khả năng chuyển tiếp.
- Giả sử
-
Hướng tiếp cận Đệ quy quay lui không nhớ (Pure Backtracking):
- Nếu tại mỗi vị trí \(j\), ta thử mọi từ trong từ điển khớp với phần đầu của
s[j..n-1]rồi gọi đệ quy cho vị trí mới \(i\), hãy xét ca kiểm thử kinh điển: \[s = \underbrace{\text{"aaaaaaaaaa"}}_{n \text{ chữ 'a'}} + \text{"b"}, \qquad \text{wordDict} = \{\text{"a"}, \text{"aa"}, \text{"aaa"}, \dots\}\] - Để đi từ chỉ số \(0\) đến chỉ số \(i = 4\), nhánh đệ quy có thể đi theo
"a"+"a"+"a"+"a", hoặc"a"+"a"+"aa", hoặc"aa"+"aa", hoặc"aaaa"... Có đúng \(2^{i-1}\) cách khác nhau cùng dẫn tới đúng một trạng thái duy nhất là đứng chờ xét phần hậu tốs[i..n]! Vì đuôi chuỗi có chữ'b'không nằm trong từ điển, mọi nhánh đều thất bại và chương trình phải duyệt hết \(\approx 2^n\) nhánh trùng lặp.
- Nếu tại mỗi vị trí \(j\), ta thử mọi từ trong từ điển khớp với phần đầu của
dp[0..10] trên chuỗi s = "bigocoding" (\(n = 10\)) với từ điển {"big", "o", "bigo", "coding"}. Từ cơ sở dp[0] = true, các mốc dp[3], dp[4] và cuối cùng là dp[10] lần lượt bật lên true nhờ các chuỗi con khớp trong từ điển.Thiết kế Quy hoạch động 1 chiều trên tiền tố chuỗi
Sự xuất hiện của các bài toán con gối nhau (cùng kiểm tra tiền tố độ dài \(i\) hoặc hậu tố bắt đầu từ \(i\)) là dấu hiệu tiêu chuẩn để áp dụng quy hoạch động 1 chiều.
Bước 1: Định nghĩa trạng thái và trường hợp cơ sở
Ta tạo mảng boolean dp kích thước \(n + 1\), trong đó:
dp[i](\(0 \le i \le n\)) mang giá trịtruenếu tiền tố gồm \(i\) ký tự đầu tiên của chuỗis(tức đoạns[0..i-1]) có thể tách thành các từ hợp lệ trongwordDict, vàfalsenếu ngược lại.- Trường hợp cơ sở:
dp[0] = true, đại diện cho tiền tố rỗng trước ký tự đầu tiên luôn hợp lệ. - Mục tiêu cần tìm: Giá trị của
dp[n].
Bước 2: Công thức chuyển trạng thái và cắt tỉa theo \(L_{\max}\)
Để tính dp[i] (\(1 \le i \le n\)), giả sử tiền tố s[0..i-1] tách được thành công, thì từ cuối cùng trong phép tách đó phải kết thúc tại chỉ số \(i - 1\) và bắt đầu tại một chỉ số \(j\) nào đó (\(0 \le j \lt i\)). Khi đó:
- Đoạn tiền tố đứng trước từ cuối cùng là
s[0..j-1]phải tách được hợp lệ, tứcdp[j] == true. - Bản thân từ cuối cùng
s[j..i-1]phải nằm trong tập từ điểnwordSet.
Gọi \(L_{\max}\) là độ dài của từ dài nhất trong wordDict. Nếu khoảng cách \(i - j \gt L_{\max}\), chuỗi con s[j..i-1] chắc chắn dài hơn mọi từ trong từ điển nên không bao giờ khớp. Vì vậy, ta chỉ cần duyệt \(j\) lùi từ \(i - 1\) về \(\max(0, i - L_{\max})\) và dừng ngay (break) khi tìm thấy một mốc \(j\) thỏa mãn:
\[\text{dp}[i] = \bigvee_{j = \max(0,\; i - L_{\max})}^{i - 1} \Big(\text{dp}[j] \;\land\; \big(s[j..i-1] \in \text{wordSet}\big)\Big)\]
Bước 3: Nâng cấp với Cây tiền tố (Trie) để loại bỏ chi phí cắt chuỗi con
Trong công thức trên, mỗi lần kiểm tra s[j..i-1] in wordSet, chương trình phải tạo chuỗi con độ dài \(L = i - j\) và tính mã băm của chuỗi con đó mất \(O(L)\) thời gian. Nếu dùng một cây tiền tố (Trie) lưu toàn bộ các từ trong wordDict:
- Thay vì đứng ở \(i\) nhìn lùi về \(j\), tại mỗi mốc \(j\) từ \(0\) đến \(n - 1\) mà
dp[j] == true, ta bắt đầu từ gốc của cây Trie và đi xuôi theo từng ký tựs[k](\(k = j, j + 1, \dots\)). - Mỗi bước nhích \(k\) sang phải chỉ tốn đúng \(O(1)\) để di chuyển sang nút con tiếp theo trên Trie (nếu không có nhánh con tương ứng thì
breakngay lập tức!). - Mỗi khi nút Trie hiện tại có cờ kết thúc từ
is_word == true, ta đánh dấu ngaydp[k + 1] = true.
| Phương pháp cài đặt | Thời gian thực thi | Bộ nhớ phụ | Khi nào ưu tiên sử dụng? |
|---|---|---|---|
| Đệ quy quay lui không nhớ | \(O(2^n)\) | \(O(n)\) | Không dùng (bị quá thời gian ngay khi \(n \ge 30\)). |
QHĐ 1 chiều + Bảng băm (HashSet) |
\(O(n \cdot L_{\max}^2 + M)\) | \(O(n + M)\) | Cài đặt nhanh nhất trong phỏng vấn khi \(L_{\max}\) nhỏ (\(\le 20\)). |
| BFS trên đồ thị chỉ số + Bảng băm | \(O(n \cdot L_{\max}^2 + M)\) | \(O(n + M)\) | Tốt khi chuỗi có rất ít mốc dp[j] == true (thưa). |
QHĐ 1 chiều + Cây tiền tố (Trie) |
\(O(n \cdot L_{\max} + M)\) | \(O(n + M)\) | Tối ưu nhất khi từ điển có nhiều từ dài chung tiền tố (\(M\) là tổng độ dài từ điển). |
Ví dụ chạy tay từng bước trên chuỗi s = "bigocoding"
Xét chuỗi s = "bigocoding" (\(n = 10\)) và từ điển wordDict = {"big", "o", "bigo", "coding"}. Độ dài từ lớn nhất là \(L_{\max} = 6\) ("coding"). Khởi tạo dp[0] = true và dp[1..10] = false.
| Chỉ số \(i\) | Tiền tố s[0..i-1] |
Các mốc \(j \in [\max(0, i-6), i-1]\) có dp[j] == true |
Chuỗi con s[j..i-1] được kiểm tra |
Có trong wordSet? |
Giá trị dp[i] |
|---|---|---|---|---|---|
| 0 | "" (rỗng) |
Cơ sở khởi tạo | — | — | true |
| 1 | "b" |
\(j = 0\) | "b" |
Không | false |
| 2 | "bi" |
\(j = 0\) | "bi" |
Không | false |
| 3 | "big" |
\(j = 0\) | "big" |
Có | true |
| 4 | "bigo" |
\(j = 3\), \(j = 0\) | \(j = 3 \to \text{"o"}\) (Có, dừng ngay!) (hoặc \(j = 0 \to \text{"bigo"}\) cũng Có) |
Có | true |
| 5..9 | "bigoc" .. "bigocodin" |
\(j \in \{0, 3, 4\}\) khi \(i \le 6\); \(j \in \{3, 4\}\) khi \(i \ge 7\) | "c", "oc", ..., "coding"[0..4] |
Không | false |
| 10 | "bigocoding" |
\(j = 4\) (vì \(10 - 6 = 4\)) | \(j = 4 \to s[4..9] = \text{"coding"}\) | Có | true |
Khi kết thúc vòng lặp tại \(i = 10\), ta thu được dp[10] = true, khẳng định chuỗi "bigocoding" có thể tách thành các từ trong từ điển (theo hai cách là "big" + "o" + "coding" hoặc "bigo" + "coding").
Cài đặt bằng C++17, Python và Java 21
Chương trình dưới đây cài đặt thuật toán quy hoạch động 1 chiều kết hợp tập băm unordered_set / set / HashSet và cắt tỉa theo độ dài từ tối đa max_len. Nếu không có dữ liệu từ luồng vào chuẩn, chương trình tự chạy trên chuỗi "applepenapple" với từ điển {"apple", "pen"} và in ra YES (tách được) hoặc NO (không tách được).
#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;
bool word_break(const string& s, const vector<string>& words) {
unordered_set<string> dict(words.begin(), words.end());
int max_len = 0;
for (const string& w : words) {
max_len = max(max_len, (int)w.size());
}
int n = (int)s.size();
vector<bool> dp(n + 1, false);
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int len = 1; len <= min(i, max_len); len++) {
int j = i - len;
if (dp[j] && dict.count(s.substr(j, len))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
int m;
if (!(cin >> s >> m)) {
cout << (word_break("applepenapple", {"apple", "pen"}) ? "YES" : "NO") << "\n";
return 0;
}
vector<string> words(m);
for (int i = 0; i < m; i++) cin >> words[i];
cout << (word_break(s, words) ? "YES" : "NO") << "\n";
return 0;
}
import sys
def word_break(s: str, words: list[str]) -> bool:
word_set = set(words)
max_len = max((len(w) for w in words), default=0)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for length in range(1, min(i, max_len) + 1):
j = i - length
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[n]
def main():
tokens = sys.stdin.read().split()
if not tokens:
print("YES" if word_break("applepenapple", ["apple", "pen"]) else "NO")
return
s = tokens[0]
m = int(tokens[1])
words = tokens[2:2 + m]
print("YES" if word_break(s, words) else "NO")
if __name__ == "__main__":
main()
import java.util.*;
public class Main {
public static boolean wordBreak(String s, List<String> words) {
Set<String> dict = new HashSet<>(words);
int maxLen = 0;
for (String w : words) maxLen = Math.max(maxLen, w.length());
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (int len = 1; len <= Math.min(i, maxLen); len++) {
int j = i - len;
if (dp[j] && dict.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
if (!sc.hasNext()) {
System.out.println(wordBreak("applepenapple", List.of("apple", "pen")) ? "YES" : "NO");
return;
}
String s = sc.next();
int m = sc.nextInt();
List<String> words = new ArrayList<>();
for (int i = 0; i < m; i++) words.add(sc.next());
System.out.println(wordBreak(s, words) ? "YES" : "NO");
}
}
Các lỗi sai thường gặp và cách tự kiểm chứng
- Lệch chỉ số giữa mảng
dp(1-indexed) và chuỗis(0-indexed): Trong mảngdp[0..n], chỉ sốiđại diện cho độ dài tiền tố (nên ký tự cuối cùng của tiền tố đó nằm ởs[i - 1]). Chuỗi con nối từ trạng tháidp[j]đếndp[i]bắt đầu tại chỉ sốjcủa chuỗisvà kết thúc tại chỉ sối - 1, có độ dài đúng bằngi - j. Trong C++ đó làs.substr(j, i - j), còn trong Python và Java (dùng cận trên không lấy) làs[j:i]vàs.substring(j, i). Nhầm thànhs.substring(j, i + 1)sẽ gây lỗi vượt biên mảng ngay ở bước cuối. - Không kiểm tra
dp[j] == truetrước khi cắt chuỗi con: Nếu bạn viếtif (word_set.count(s.substr(j, i - j)) && dp[j]), ngôn ngữ lập trình sẽ thực hiện lệnh cấp phát bộ nhớ và băm chuỗi cons.substr(j, i - j)ở mọi chỉ số \(j\) trước rồi mới kiểm tradp[j]. Đặtif (!dp[j]) continue;lên dòng đầu tiên của vòng lặp trong giúp bỏ qua ngay lập tức mọi vị trí \(j\) bằngfalsetrong \(O(1)\) mà không tốn một byte cấp phát chuỗi nào. - Cách tự kiểm chứng tại nhà: Khi tự kiểm tra code, bạn hãy thử ba nhóm ca kiểm thử đặc biệt: (1) ca tham lam bẫy như
s = "aaaaaa"với{"aaaa", "aaa"}(phải raYES) vàs = "catsandog"với{"cats", "dog", "sand", "and", "cat"}(phải raNO); (2) ca một từ được lặp lại nhiều lần nhưs = "applepenapple"với{"apple", "pen"}; và (3) ca đo hiệu năng chống nổ tổ hợp gồm \(200\) chữ'a'nối thêm chữ'b'ở cuối với từ điển{"a", "aa", "aaa", "aaaa"}(phải raNOdưới \(1\text{ ms}\)).
Luyện ngay trên Big-O Coding
Để rèn luyện kỹ năng kết hợp quy hoạch động trên chuỗi với cây tiền tố Trie và quay lui phân hoạch chuỗi, bạn hãy thực hành ngay bộ ba bài toán dưới đây trong lộ trình Coding Interview 150:
Nếu đề bài yêu cầu đếm tổng số cách tách từ khác nhau thì sửa công thức như thế nào?
Thay vì lưu giá trị boolean true/false trong dp[i], bạn đổi dp[i] thành số nguyên đếm số cách tách tiền tố độ dài \(i\), khởi tạo dp[0] = 1. Tại mỗi bước \(i\), thay vì break ngay khi gặp một điểm cắt \(j\) hợp lệ, bạn cộng dồn tất cả các điểm cắt hợp lệ: \(\text{dp}[i] = \sum \text{dp}[j]\) với mọi \(j\) thỏa mãn s[j..i-1] in wordSet (thường lấy phần dư theo modulo \(10^9 + 7\) để tránh tràn số). Chẳng hạn với "bigocoding" và từ điển {"big", "o", "bigo", "coding"}, ta có dp[3] = 1, dp[4] = dp[3] + dp[0] = 2, và dp[10] = dp[4] = 2 cách tách.
Làm thế nào để giải bài toán mở rộng Word Break II (LeetCode 140 — liệt kê toàn bộ các câu tách được)?
Trong Word Break II, đề bài yêu cầu trả về danh sách tất cả các câu hoàn chỉnh sau khi chèn dấu cách. Vì tổng số câu đầu ra trong trường hợp xấu nhất có thể lên tới \(O(2^n)\), cách hiệu quả nhất là:
- Chạy trước mảng boolean
dp[0..n](hoặc đánh dấu các chỉ số có thể đi tới đíchn) để làm bộ lọc cắt tỉa. - Viết hàm đệ quy có nhớ (DFS + Memoization)
dfs(start)trả về danh sách các câu tạo từ hậu tốs[start..n-1], hoặc quay lui từ0đếnnnhưng chỉ bước vào nhánhnext_idxnếucan_reach_end[next_idx] == true. Bước lọc này giúp tránh toàn bộ các nhánh cụt tốn thời gian vô ích.
Khi nào nên nhìn bài toán Word Break như thuật toán BFS trên đồ thị có hướng?
Ta có thể coi các chỉ số \(0, 1, \dots, n\) là \(n + 1\) đỉnh của một đồ thị có hướng (DAG): tồn tại cạnh có hướng từ đỉnh \(j\) sang đỉnh \(i\) (\(j \lt i\)) nếu chuỗi con s[j..i-1] nằm trong từ điển. Khi đó, bài toán Word Break chính là kiểm tra xem có đường đi từ đỉnh \(0\) tới đỉnh \(n\) hay không. Nếu đề bài hỏi thêm "Cần ít nhất bao nhiêu từ trong từ điển để ghép thành chuỗi s?", thì đó chính là bài toán tìm đường đi ngắn nhất không trọng số từ đỉnh \(0\) đến đỉnh \(n\), giải trực tiếp bằng thuật toán BFS.
Luyện LeetCode thực chiến theo pattern, giải bài trong 45 phút và mock interview cùng AI. 16 buổi online, lớp 7–12 học viên, chọn C++, Java hoặc Python.


