The trick here is to name the state correctly, then let the implementation follow. For 1408. String Matching in an Array, the solution in this repository is mainly a prefix sums solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. 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: prefix sums, greedy.
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are stringMatching, add, get, build, lps.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- Sorting is used to make local choices comparable, so the later scan does not have to rediscover order.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- 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(NlogN + N * S^2), where S is the max length of all words.
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Runtime: 8 ms, faster than 40.00% of C++ online submissions for String Matching in an Array.
02//Memory Usage: 8.6 MB, less than 100.00% of C++ online submissions for String Matching in an Array.
03class Solution {
04public:
05 vector<string> stringMatching(vector<string>& words) {
06 int n = words.size();
07
08 set<string> ans;
09
10 for(int i = 0; i < n; i++){
11 for(int j = 0; j < n; j++){
12 if(i != j && words[i].find(words[j]) != string::npos){
13 ans.insert(words[j]);
14 }
15 }
16 }
17
18 return vector<string>(ans.begin(), ans.end());
19 }
20};
21
22class Node{
23public:
24 vector<Node*> children;
25
26 Node(){
27 children = vector<Node*>(26, nullptr);
28 }
29};
30
31class SuffixTree{
32public:
33 Node* root = new Node();
34
35 void add(string& word){
36 Node* cur = root;
37 for(char c: word){
38 if(cur->children[c-'a'] == nullptr){
39 cur->children[c-'a'] = new Node();
40 }
41 cur = cur->children[c-'a'];
42 }
43 };
44
45 bool get(string& word){
46 Node* cur = root;
47 for(char c : word){
48 if(cur->children[c-'a'] == nullptr){
49 return false;
50 }
51 cur = cur->children[c-'a'];
52 }
53 return true;
54 };
55};
56
57//Suffix tree
58//https://leetcode.com/problems/string-matching-in-an-array/discuss/575147/Clean-Python-3-suffix-trie-O(NlogN-%2B-N-*-S2)
59//Time: O(NlogN + N * S^2), where S is the max length of all words.
60//NlogN for sorting and N * S^2 for build suffix trie.
61//Space: O(N * S^2) for suffix trie
62//Runtime: 28 ms, faster than 29.06% of C++ online submissions for String Matching in an Array.
63//Memory Usage: 29.1 MB, less than 100.00% of C++ online submissions for String Matching in an Array.
64class Solution {
65public:
66 vector<string> stringMatching(vector<string>& words) {
67 SuffixTree* st = new SuffixTree();
68 vector<string> ans;
69
70 //sort by their length, descending
71 //because the longer word cannot be a suffix of a shorter word
72 sort(words.begin(), words.end(), [](string& a, string& b){
73 return a.size() > b.size();
74 });
75
76 for(string& word : words){
77 // cout << word << endl;
78 if(st->get(word)){
79 ans.push_back(word);
80 }
81 //add suffix of word into the suffix tree
82 for(int i = 0; i < word.size(); i++){
83 string suffix = word.substr(i, word.size()-i);
84 st->add(suffix);
85 }
86 }
87
88 return ans;
89 }
90};
91
92//counting on trie nodes in suffix tree
93//https://leetcode.com/problems/string-matching-in-an-array/discuss/575147/Clean-Python-3-suffix-trie-O(NlogN-%2B-N-*-S2)
94//Runtime: 36 ms, faster than 23.11% of C++ online submissions for String Matching in an Array.
95//Memory Usage: 29 MB, less than 100.00% of C++ online submissions for String Matching in an Array.
96//time: O(N * S^2), space: O(N * S^2)
97class Node{
98public:
99 vector<Node*> children;
100 int count;
101
102 Node(){
103 children = vector<Node*>(26, nullptr);
104 count = 0;
105 }
106};
107
108class SuffixTree{
109public:
110 Node* root = new Node();
111
112 void add(string& word){
113 Node* cur = root;
114 for(char c: word){
115 if(cur->children[c-'a'] == nullptr){
116 cur->children[c-'a'] = new Node();
117 }
118 cur = cur->children[c-'a'];
119 //first go to that child and then increase its visit count
120 cur->count += 1;
121 // cout << c << " " << cur->count << " | ";
122 }
123 // cout << endl;
124 };
125
126 bool get(string& word){
127 Node* cur = root;
128 for(char c : word){
129 if(cur->children[c-'a'] == nullptr){
130 return false;
131 }
132 cur = cur->children[c-'a'];
133 }
134 // cout << word << " " << cur->count << endl;
135 //if cur has been visited more than once, it's a suffix of others
136 return cur->count > 1;
137 };
138};
139
140class Solution {
141public:
142 vector<string> stringMatching(vector<string>& words) {
143 SuffixTree* st = new SuffixTree();
144 vector<string> ans;
145
146 for(string& word : words){
147 //add suffix of word into the suffix tree
148 for(int i = 0; i < word.size(); i++){
149 string suffix = word.substr(i, word.size()-i);
150 st->add(suffix);
151 }
152 }
153
154 for(string& word : words){
155 if(st->get(word)){
156 ans.push_back(word);
157 }
158 }
159
160 return ans;
161 }
162};
163
164//KMP
165//https://leetcode.com/problems/string-matching-in-an-array/discuss/576070/C%2B%2B-concise-KMP-solution-beats-20!
166//Runtime: 24 ms, faster than 32.68% of C++ online submissions for String Matching in an Array.
167//Memory Usage: 10.8 MB, less than 100.00% of C++ online submissions for String Matching in an Array.
168class Solution {
169public:
170 vector<int> build(string& pat){
171 int n = pat.size();
172 vector<int> lps(n, 0);
173
174 for(int i = 1, len = 0; i < n; ){
175 if(pat[i] == pat[len]){
176 len++;
177 lps[i] = len;
178 i++;
179 }else if(len > 0){
180 //fallback to compare with a shorter prefix/suffix
181 len = lps[len-1];
182 }else{
183 //len equals to 0 here
184 lps[i] = 0;
185 i++;
186 }
187 }
188
189 return lps;
190 };
191
192 bool search(string& text, string& pat){
193 int m = text.size(), n = pat.size();
194 if(n == 0) return false;
195
196 vector<int> lps = build(pat);
197
198 for(int i = 0, j = 0; i < m; ){
199 if(text[i] == pat[j]){
200 i++;
201 j++;
202 }
203
204 if(j == n){
205 return true;
206 }
207
208 if(i < m && text[i] != pat[j]){
209 if(j > 0){
210 //j now serves as len in bulid()
211 j = lps[j-1];
212 }else{
213 i++;
214 }
215 }
216 }
217
218 return false;
219 };
220
221 vector<string> stringMatching(vector<string>& words) {
222 vector<string> ans;
223
224 //sort by length, ascending
225 sort(words.begin(), words.end(), [](string& a, string& b){
226 return a.size() < b.size();
227 });
228
229 for(int pi = 0; pi < words.size(); pi++){
230 //examine pattern one by one
231 for(int ti = pi+1; ti < words.size(); ti++){
232 if(search(words[ti], words[pi])){
233 ans.push_back(words[pi]);
234 //if words[pi] is a substring of any longer words, break at once so that there won't be duplicate element in ans
235 break;
236 }
237 }
238 }
239
240 return ans;
241 }
242};Cost
Complexity
Time
O(NlogN + N * S^2), where S is the max length of all words.
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.