I like to read this solution as a small machine: keep the useful information, throw away the noise. For 1397. Find All Good Strings, the solution in this repository is mainly a DFS + memoization solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. 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: DFS + memoization, dynamic programming.
The notes already sitting in the source point us in the right direction:
- KMP + DFS + Memo
- https://leetcode.com/problems/find-all-good-strings/discuss/554806/O(N-*-len(evil))-Solution-with-memorized-DP-and-KMP-algorithm
- TLE
- 53 / 53 test cases passed, but took too long.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are computeLPSArray, count, findGoodStrings.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- 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:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
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) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//KMP + DFS + Memo
02//https://leetcode.com/problems/find-all-good-strings/discuss/554806/O(N-*-len(evil))-Solution-with-memorized-DP-and-KMP-algorithm
03//TLE
04//53 / 53 test cases passed, but took too long.
05class Solution {
06public:
07 int n;
08 int m;
09 int mod;
10 string s1, s2, evil;
11 vector<int> lps;
12 unordered_map<string, int> memo;
13
14 void computeLPSArray(){
15 int n = evil.size();
16 lps = vector<int>(n, 0);
17
18 for(int i = 1, len = 0; i < n; ){
19 if(evil[i] == evil[len]){
20 len++;
21 lps[i] = len;
22 i++;
23 }else if(len > 0){
24 len = lps[len-1];
25 }else{
26 lps[i] = 0;
27 i++;
28 }
29 }
30 };
31
32 int count(int idx, bool pre1, bool pre2, int preE){
33 //we just construct evil
34 if(preE == m) return 0;
35 //we just construct one valid string
36 if(idx == n) return 1;
37
38 string hashKey = to_string(idx) + "$" + to_string(pre1) + "$" + to_string(pre2) + "$" + to_string(preE);
39 if(memo.find(hashKey) != memo.end()){
40 return memo[hashKey];
41 }
42
43 int total = 0;
44 //the first and last possible char of current position
45 char first = pre1 ? s1[idx] : 'a';
46 char last = pre2 ? s2[idx] : 'z';
47
48 for(int i = first-'a'; i <= last-'a'; i++){
49 char c = i+'a';
50
51 bool _pre1 = pre1 && (first == c);
52 bool _pre2 = pre2 && (last == c);
53
54 int _preE = preE;
55 while(_preE!=0 && c != evil[_preE]){
56 _preE = lps[_preE-1];
57 }
58 if(c == evil[_preE]){
59 _preE++;
60 }
61
62 total += count(idx+1, _pre1, _pre2, _preE);
63 total %= mod;
64 }
65
66 memo[hashKey] = total;
67
68 return total;
69 };
70
71 int findGoodStrings(int n, string s1, string s2, string evil) {
72 this->n = n;
73 this->s1 = s1;
74 this->s2 = s2;
75 this->evil = evil;
76 this->m = evil.size();
77 this->mod = 1e9+7;
78 computeLPSArray();
79
80 return count(0, true, true, 0);
81 }
82};
83
84//KMP + DFS + Memo
85//use 4-D vector instead of unordered_map to speed up
86//https://leetcode.com/problems/find-all-good-strings/discuss/555591/JavaC%2B%2B-Memoization-DFS-and-KMP-with-Picture-Clean-code
87//Runtime: 108 ms, faster than 43.06% of C++ online submissions for Find All Good Strings.
88//Memory Usage: 18.5 MB, less than 100.00% of C++ online submissions for Find All Good Strings.
89class Solution {
90public:
91 int n;
92 int m;
93 int mod;
94 string s1, s2, evil;
95 vector<int> lps;
96 vector<vector<vector<vector<int>>>> memo;
97
98 void computeLPSArray(){
99 int n = evil.size();
100 lps = vector<int>(n, 0);
101
102 for(int i = 1, len = 0; i < n; ){
103 if(evil[i] == evil[len]){
104 len++;
105 lps[i] = len;
106 i++;
107 }else if(len > 0){
108 len = lps[len-1];
109 }else{
110 lps[i] = 0;
111 i++;
112 }
113 }
114 };
115
116 int count(int idx, bool pre1, bool pre2, int preE){
117 //we just construct evil
118 if(preE == m) return 0;
119 //we just construct one valid string
120 if(idx == n) return 1;
121
122 if(memo[idx][preE][pre1][pre2] != -1){
123 return memo[idx][preE][pre1][pre2];
124 }
125
126 int total = 0;
127 //the first and last possible char of current position
128 char first = pre1 ? s1[idx] : 'a';
129 char last = pre2 ? s2[idx] : 'z';
130
131 for(int i = first-'a'; i <= last-'a'; i++){
132 char c = i+'a';
133
134 bool _pre1 = pre1 && (first == c);
135 bool _pre2 = pre2 && (last == c);
136
137 int _preE = preE;
138 while(_preE!=0 && c != evil[_preE]){
139 _preE = lps[_preE-1];
140 }
141 if(c == evil[_preE]){
142 _preE++;
143 }
144
145 total += count(idx+1, _pre1, _pre2, _preE);
146 total %= mod;
147 }
148
149 memo[idx][preE][pre1][pre2] = total;
150
151 return total;
152 };
153
154 int findGoodStrings(int n, string s1, string s2, string evil) {
155 this->n = n;
156 this->s1 = s1;
157 this->s2 = s2;
158 this->evil = evil;
159 this->m = evil.size();
160 this->mod = 1e9+7;
161 this->memo = vector(n+1, vector(evil.size()+1, vector(2, vector(2, -1))));
162 computeLPSArray();
163
164 return count(0, true, true, 0);
165 }
166};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
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.