139. Word Break
Tags:
Medium
Skills:
TrieDP
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu kiểm tra xem một chuỗi s có thể được phân tách thành một chuỗi các từ (có thể lặp lại) từ danh sách từ điển wordDict hay không
Approach - DP
s[j:i] thuộc wordDict, thì đặt dp[i] = trueTime and space complexity
s (vì với mỗi i duyệt qua tối đa i lần j)dp và O(m) cho set từ điểnSolution
1function wordBreak(s: string, wordDict: string[]): boolean {
2 const word_set = new Set(wordDict);
3 const n = s.length;
4 const dp: boolean[] = new Array(n + 1).fill(false)
5 dp[0] = true; // empty string is true
6
7 for(let i = 0; i <= n; i++) {
8 for(let j =0 ; j < i; j++) {
9 if(dp[j] && word_set.has(s.substring(j, i))) {
10 dp[i] = true;
11 break;
12 }
13 }
14 }
15 return dp[n];
16};word_set : Tra cứu từ điển nhanh O(1)\dp[i] : true nếu s[0:i] tách hợp lệi , break để tiết kiệm thời giandp[i] lưu trạng thái: s[0:i] có thể tách thành các từ hợp lệ khôngi , kiểm tra mọi điểm cắt j trước đó. Nếu dp[j] = true và s[j:i] nằm trong từ điển thì dp[i] = trueSolution - optimize with trie
1class TrieNode {
2 children: Map<string, TrieNode>;
3 is_word: boolean
4 constructor() {
5 this.children = new Map();
6 this.is_word = false;
7 }
8}
9
10class Trie {
11 root: TrieNode;
12
13 constructor() {
14 this.root = new TrieNode();
15 }
16
17 insert(word: string): void {
18 let node = this.root;
19 for (const char of word) {
20 if (!node.children.has(char)) {
21 node.children.set(char, new TrieNode());
22 }
23 node = node.children.get(char);
24 }
25
26 node.is_word = true;
27 }
28
29 searchPrefix(prefix: string): boolean {
30 let node = this.root;
31 for (const char of prefix) {
32 if (!node.children.has(char)) {
33 return false;
34 }
35 node = node.children.get(char);
36 }
37 return true
38 }
39
40 searchWord(word: string): boolean {
41 let node = this.root;
42 for (const char of word) {
43 if (!node.children.has(char)) {
44 return false;
45 }
46 node = node.children.get(char);
47 }
48 return node.is_word;
49 }
50}
51
52function wordBreak(s: string, wordDict: string[]): boolean {
53 const trie = new Trie();
54 for (const word of wordDict) {
55 trie.insert(word)
56 }
57
58 const n = s.length;
59 const dp: boolean[] = new Array(n + 1).fill(false)
60 dp[0] = true; // empty string is true
61
62 for (let i = 0; i <= n; i++) {
63 for (let j = 0; j < i; j++) {
64 if (dp[j] && trie.searchWord(s.substring(j, i))) {
65 dp[i] = true;
66 break;
67 }
68 }
69 }
70 return dp[n];
71};Trie không tối ưu hơn Set về mặt SC, và thực tế cả hai đều có cùng độ phức tạp SC là O(m), với m là tổng số ký tự của toàn bộ từ điển