I like to read this solution as a small machine: keep the useful information, throw away the noise. For 214. Shortest Palindrome, the solution in this repository is mainly a two pointers 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: two pointers.
The notes already sitting in the source point us in the right direction:
- Brute force
- TLE
- 119 / 120 test cases passed.
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 isPalindrome, shortestPalindrome, srev, lps, t.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- 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:
- 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^2), space: O(N)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Brute force
02//TLE
03//119 / 120 test cases passed.
04class Solution {
05public:
06 bool isPalindrome(string s){
07 int n = s.size();
08
09 for(int i = 0; i < n-1-i; ++i){
10 if(s[i] != s[n-1-i]){
11 return false;
12 }
13 }
14
15 return true;
16 };
17
18 string shortestPalindrome(string s) {
19 int n = s.size();
20
21 for(int l = n; l >= 1; --l){
22 if(isPalindrome(s.substr(0, l))){
23 string prepend = s.substr(l);
24 reverse(prepend.begin(), prepend.end());
25 return prepend + s;
26 }
27 }
28
29 return "";
30 }
31};
32
33//Approach #1 Brute force [Accepted]
34//TLE
35//119 / 120 test cases passed.
36//time: O(N^2), space: O(N)
37class Solution {
38public:
39 string shortestPalindrome(string s) {
40 int n = s.size();
41 string srev(s.rbegin(), s.rend());
42
43 /*
44 s: "aacecaaa"
45 srev: "aaacecaa"
46 */
47 for(int l = n; l >= 1; --l){
48 if(s.substr(0, l) == srev.substr(n-l)){
49 return srev.substr(0, n-l) + s;
50 }
51 }
52
53 return "";
54 }
55};
56
57//Approach #2 Two pointers and recursion [Accepted]
58//Runtime: 8 ms, faster than 96.25% of C++ online submissions for Shortest Palindrome.
59//Memory Usage: 7.2 MB, less than 93.85% of C++ online submissions for Shortest Palindrome.
60//time: O(N^2), space: O(N)
61class Solution {
62public:
63 string shortestPalindrome(string s) {
64 int n = s.size();
65
66 int i = 0;
67 for(int j = n-1; j >= 0; --j){
68 if(s[i] == s[j]){
69 ++i;
70 }
71 }
72
73 //there are "i(=n)" char matched
74 if(i == n) return s;
75
76 //the unmatched part
77 string remain = s.substr(i);
78 string remain_rev = remain;
79 reverse(remain_rev.begin(), remain_rev.end());
80
81 // cout << "i: " << i << ", " << remain_rev << " + ... + " << remain << endl;
82 return remain_rev + shortestPalindrome(s.substr(0, i)) + remain;
83 }
84};
85
86//Approach #3 KMP [Accepted]
87//Runtime: 8 ms, faster than 96.25% of C++ online submissions for Shortest Palindrome.
88//Memory Usage: 8.2 MB, less than 19.45% of C++ online submissions for Shortest Palindrome.
89//time: O(N), space: O(N)
90class Solution {
91public:
92 string shortestPalindrome(string s) {
93 int n = s.size();
94 string srev(s.rbegin(), s.rend());
95 string snew = s + "#" + srev;
96 int nnew = snew.size();
97 vector<int> lps(nnew, 0);
98
99 // cout << "snew: " << snew << endl;
100 for(int i = 1, len = 0; i < nnew; /*no i++ here!*/){
101 // cout << "i: " << i << " ";
102 if(snew[i] == snew[len]){
103 // cout << i << " and " << len << " match" << endl;
104 ++len;
105 lps[i] = len;
106 ++i;
107 }else{
108 if(len > 0){
109 //fallback
110 // cout << "fallback from " << len << " to " << lps[len-1] << endl;
111 len = lps[len-1];
112 }else{
113 // cout << "move i forward" << endl;
114 lps[i] = 0;
115 ++i;
116 }
117 }
118 }
119
120 // for(int i = 0; i < nnew; ++i){
121 // cout << "lps[" << i << "]: " << lps[i] << endl;
122 // }
123
124 /*
125 for s: aacecaaa, (n = 8)
126 snew: aacecaaa#aaacecaa (nnew = 17)
127 "aacecaa" starting from 0 match "aacecaa" starting from 10,
128 i.e. for the srev "aaacecaa", it starts the match from its index 1.
129 Note that lps[nnew-1] is 7(the former 7 chars of s match the later 7 chars of srev).
130 So we only need one more char to make "s" a palindrome
131 */
132 return srev.substr(0, n - lps[nnew-1]) + s;
133 }
134};
135
136//Approach #3 KMP [Accepted](official)
137//Runtime: 8 ms, faster than 96.25% of C++ online submissions for Shortest Palindrome.
138//Memory Usage: 7.9 MB, less than 66.73% of C++ online submissions for Shortest Palindrome.
139class Solution {
140public:
141 string shortestPalindrome(string s) {
142 int n = s.size();
143 string srev(s.rbegin(), s.rend());
144 string snew = s + "#" + srev;
145 int nnew = snew.size();
146 vector<int> lps(nnew, 0);
147
148 for(int i = 1; i < nnew; ++i){
149 int len = lps[i-1];
150 while(len > 0 && snew[i] != snew[len]){
151 len = lps[len-1];
152 }
153 if(snew[i] == snew[len]){
154 ++len;
155 }
156 lps[i] = len;
157 }
158 return srev.substr(0, n - lps[nnew-1]) + s;
159 }
160};
161
162//Rolling hash, Rabin-Karp
163//https://leetcode.com/problems/shortest-palindrome/discuss/60153/8-line-O(n)-method-using-Rabin-Karp-rolling-hash
164//Runtime: 8 ms, faster than 96.25% of C++ online submissions for Shortest Palindrome.
165//Memory Usage: 7.1 MB, less than 98.13% of C++ online submissions for Shortest Palindrome.
166class Solution {
167public:
168 string shortestPalindrome(string s) {
169 int n = s.size();
170
171 int MOD = 1e9+7;
172 int len = 0;
173 //all variable used in multiplication should be declared as "long long"
174 long long p;
175 long long B = 29;
176 long long hash1 = 0, hash2 = 0;
177
178 for(int i = 0, p = 1L; i < n; ++i, p = (p * B) % MOD){
179 //all variable used in multiplication should be declared as "long long"
180 long long d = s[i]-'a';
181 hash1 = (hash1 * B + d) % MOD;
182 hash2 = (hash2 + d * p) % MOD;
183 //the length of palindrome
184 if(hash1 == hash2) len = i+1;
185 }
186
187 string prepend = s.substr(len);
188 reverse(prepend.begin(), prepend.end());
189
190 return prepend + s;
191 }
192};
193
194//Manacher's algorithm
195//https://leetcode.com/problems/shortest-palindrome/discuss/60234/Easy-C%2B%2B-Manacher
196//Runtime: 12 ms, faster than 61.90% of C++ online submissions for Shortest Palindrome.
197//Memory Usage: 7.8 MB, less than 70.16% of C++ online submissions for Shortest Palindrome.
198class Solution {
199public:
200 string shortestPalindrome(string s) {
201 int n = s.size();
202 int tn = 2*n+3;
203
204 /*
205 s: abcd
206 t: ^#a#b#c#d#$
207 */
208 string t(tn, '#');
209
210 t[0] = '^';
211 t[t.size()-1] = '$';
212
213 for(int i = 2, j = 0; j < n; i += 2, ++j){
214 t[i] = s[j];
215 }
216
217 // cout << t << endl;
218
219 int mirror = 0, right = 0, center = 0;
220 vector<int> p(tn, 0);
221
222 for(int i = 0; i < tn; ++i){
223 //i - center == center - mirror
224 mirror = center*2 - i;
225
226 if(i < right){
227 p[i] = min(p[mirror], right - i);
228 }
229
230 while(i+p[i]+1 < tn && i-(p[i]+1) >= 0 && t[i-(p[i]+1)] == t[i+p[i]+1]){
231 ++p[i];
232 }
233
234 if(i+p[i] > right){
235 center = i;
236 right = center + p[center];
237 }
238 }
239
240 /*
241 find in t[1:tn-2]: #a#b#c#d#
242 */
243 int not_match_start;
244 for (int i = tn - 2; i > 0; i--) {
245 // cout << i << " - " << p[i] << endl;
246 //i: the center of palindrome
247 //p[i]: the length of half palindrome in t
248 //i - p[i]: the start index of palindrome in t
249 //here we choose the palindrome starting at 1?
250 if (i - p[i] == 1) {
251 not_match_start = p[i];
252 break;
253 }
254 }
255 string not_match = s.substr(not_match_start);
256 reverse(not_match.begin(), not_match.end());
257 return not_match + s;
258 }
259};Cost
Complexity
Time
O(N^2), space: O(N)
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.