The trick here is to name the state correctly, then let the implementation follow. For 139. Word Break, the solution in this repository is mainly a trie solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: trie, dynamic programming.
The notes already sitting in the source point us in the right direction:
- DP
- time: O(N^3), substr takes O(N)
- space: O(N)
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are wordBreak, add.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- Substring checks are convenient but not free, so they are part of the real complexity story.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(N^3), substr takes O(N)
- Space: O(N)
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//DP
02//Runtime: 28 ms, faster than 48.19% of C++ online submissions for Word Break.
03//Memory Usage: 10.8 MB, less than 61.87% of C++ online submissions for Word Break.
04//time: O(N^3), substr takes O(N)
05//space: O(N)
06class Solution {
07public:
08 bool wordBreak(string s, vector<string>& wordDict) {
09 int n = s.size();
10 vector<bool> dp(n+1, false);
11 //padding, assume empty string is a valid dictionary word
12 dp[n] = true;
13
14 for(int i = n-1; i >= 0; --i){
15 dp[i] = find(wordDict.begin(), wordDict.end(), s.substr(i)) != wordDict.end();
16
17 /*
18 split s[i:] into s[i:j-1] and s[j:],
19 and see if the split is valid
20 */
21 for(int j = n; j >= i+1; --j){
22 //s[j:] is composed by valid dictionary words
23 //and s[i:j-1] is a valid dictionary word
24 dp[i] = dp[j] && find(wordDict.begin(), wordDict.end(), s.substr(i, j-i)) != wordDict.end();
25 if(dp[i]) break;
26 }
27 }
28
29 return dp[0];
30 }
31};
32
33//DP optimized from above
34//Runtime: 12 ms, faster than 79.03% of C++ online submissions for Word Break.
35//Memory Usage: 9.6 MB, less than 68.61% of C++ online submissions for Word Break.
36class Solution {
37public:
38 bool wordBreak(string s, vector<string>& wordDict) {
39 int n = s.size();
40
41 vector<bool> dp(n+1, false);
42 dp[n] = true;
43
44 for(int i = n-1; i >= 0; --i){
45 for(int j = i+1; j <= n; ++j){
46 // cout << i << ", " << j << ", " << s.substr(i, j-i) << endl;
47 if(dp[j] && find(wordDict.begin(), wordDict.end(), s.substr(i, j-i)) != wordDict.end()){
48 dp[i] = true;
49 break;
50 }
51 }
52 }
53
54 return dp[0];
55 }
56};
57
58//DP
59//https://leetcode.com/problems/concatenated-words/discuss/348972/Java-Common-template-Word-Break-I-Word-Break-II-Concatenated-Words
60//Runtime: 28 ms, faster than 49.06% of C++ online submissions for Word Break.
61//Memory Usage: 12.9 MB, less than 52.89% of C++ online submissions for Word Break.
62class Solution {
63public:
64 bool wordBreak(string s, vector<string>& wordDict) {
65 int n = s.size();
66
67 //key: end index, 1-based
68 vector<bool> dp(n+1, false);
69 //empty string
70 dp[0] = true;
71
72 for(int end = 1; end <= n; ++end){
73 for(int start = 0; start < end; ++start){
74 //dp[start]: s[0...start-1]
75 if(dp[start] && find(wordDict.begin(), wordDict.end(), s.substr(start, end-start)) != wordDict.end()){
76 //s[0...end-1] can be split into s[0...start-1] and s[start...end-1]
77 dp[end] = true;
78 break;
79 }
80 }
81 }
82
83 return dp[n];
84 }
85};
86
87//trie
88//Runtime: 24 ms, faster than 56.77% of C++ online submissions for Word Break.
89//Memory Usage: 13.7 MB, less than 26.97% of C++ online submissions for Word Break.
90class TrieNode {
91public:
92 vector<TrieNode*> children;
93 bool end;
94
95 TrieNode(){
96 children = vector<TrieNode*>(26, nullptr);
97 end = false;
98 }
99};
100
101class Trie {
102public:
103 TrieNode* root;
104
105 Trie(){
106 root = new TrieNode();
107 }
108
109 void add(string& word){
110 TrieNode* cur = root;
111 for(char c : word){
112 if(!cur->children[c-'a']){
113 cur->children[c-'a'] = new TrieNode();
114 }
115 cur = cur->children[c-'a'];
116 }
117 cur->end = true;
118 }
119
120 bool find(string word){
121 TrieNode* cur = root;
122 for(char c : word){
123 if(!cur->children[c-'a']){
124 return false;
125 }
126 cur = cur->children[c-'a'];
127 }
128 return cur->end;
129 }
130};
131
132class Solution {
133public:
134 bool wordBreak(string s, vector<string>& wordDict) {
135 int n = s.size();
136 vector<bool> dp(n+1, false);
137 dp[n] = true;
138
139 Trie* trie = new Trie();
140
141 for(string& word : wordDict){
142 trie->add(word);
143 }
144
145 for(int i = n-1; i >= 0; --i){
146 dp[i] = trie->find(s.substr(i));
147
148 for(int j = n; j >= i+1; --j){
149 dp[i] = dp[j] && trie->find(s.substr(i, j-i));
150 if(dp[i]) break;
151 }
152 }
153
154 return dp[0];
155 }
156};Cost
Complexity
Time
O(N^3), substr takes O(N)
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(N)
Auxiliary state plus the answer structure where the problem requires one.