Let's make this one less mysterious. For 564. Find the Closest Palindrome, the solution in this repository is mainly a straightforward implementation 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: straightforward implementation.
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 choose, nearestPalindromic.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- 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:
- 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//Runtime: 4 ms, faster than 59.37% of C++ online submissions for Find the Closest Palindrome.
02//Memory Usage: 6.3 MB, less than 54.60% of C++ online submissions for Find the Closest Palindrome.
03class Solution {
04public:
05 string n;
06
07 string choose(string& s1, string& s2){
08 if(abs(stoll(s1)-stoll(n)) == abs(stoll(s2)-stoll(n))){
09 return (stoll(s1) < stoll(s2)) ? s1 : s2;
10 }else{
11 return (abs(stoll(s1)-stoll(n)) < abs(stoll(s2)-stoll(n))) ? s1 : s2;
12 }
13 };
14
15 string nearestPalindromic(string n) {
16 this->n = n;
17 int sz = n.size();
18
19 if(sz == 1){
20 if(n == "0"){
21 return "-1";
22 }else{
23 n[0] -= 1;
24 return n;
25 }
26 }
27
28 string ans = n;
29 for(int i = 0; i < sz >> 1; ++i){
30 ans[sz-1-i] = n[i];
31 }
32
33 if(ans > n){
34 // cout << "ans larger" << endl;
35 if(sz & 1){
36 string s1 = ans;
37 if(s1[sz>>1] > '0') s1[sz>>1] -= 1;
38 ans = choose(s1, ans);
39
40 s1 = string(sz-1, '9');
41 // cout << s1 << " v.s. " << ans << endl;
42 ans = choose(s1, ans);
43 }else{
44 // cout << "length even" << endl;
45 string s1 = ans;
46 if(s1[sz>>1] > '0') s1[(sz>>1)-1] = s1[sz>>1] = ans[sz>>1] - 1;
47 // cout << s1 << " v.s. " << ans << endl;
48 ans = choose(s1, ans);
49
50 s1 = string(sz-1, '9');
51 // cout << s1 << " v.s. " << ans << endl;
52 ans = choose(s1, ans);
53 }
54 }else{
55 if(sz & 1){
56 string s1 = ans;
57 if(s1[sz>>1] < '9') s1[sz>>1] += 1;
58 ans = choose(s1, ans);
59 }else{
60 string s1 = ans;
61 if(s1[sz>>1] < '9') s1[(sz>>1)-1] = s1[sz>>1] = ans[sz>>1] + 1;
62 ans = choose(s1, ans);
63 }
64 }
65
66 if(ans == n){
67 //n is already a palindrome
68 if(sz & 1){
69 // cout << "sz odd" << endl;
70 if(n[sz>>1] == '0'){
71 // cout << "middle 0" << endl;
72 string s1 = n;
73 s1[sz>>1] = n[sz>>1] + 1;
74
75 string s2 = n;
76 s2[sz>>1] = '9';
77 int shift = 1;
78 while((sz>>1)-shift >= 0 && s2[(sz>>1)-shift] == '0'){
79 s2[(sz>>1)-shift] = s2[(sz>>1)+shift] = '9';
80 ++shift;
81 }
82
83 if((sz>>1)-shift >= 0){
84 if((sz>>1)-shift == 0 && s2[0] == '1'){
85 s2 = string(sz-1, '9');
86 }else{
87 s2[(sz>>1)-shift] = s2[(sz>>1)+shift] = n[(sz>>1)+shift]-1;
88 }
89 // cout << s1 << " v.s. " << s2 << endl;
90 ans = choose(s1, s2);
91 }else{
92 ans = "-1";
93 }
94 }else if(n[sz>>1] == '9'){
95 // cout << "middle 9" << endl;
96 string s1 = n;
97 s1[sz>>1] = n[sz>>1] - 1;
98
99 string s2 = n;
100 s2[sz>>1] = '0';
101 int mid = sz>>1;
102 int shift = 1;
103 while((sz>>1)-shift >= 0 && s2[(sz>>1)-shift] == '9'){
104 s2[(sz>>1)-shift] = s2[(sz>>1)+shift] = '0';
105 ++shift;
106 }
107 if((sz>>1)-shift >= 0){
108 s2[(sz>>1)-shift] = s2[(sz>>1)+shift] = n[(sz>>1)+shift]+1;
109 // cout << s1 << " v.s. " << s2 << endl;
110 ans = choose(s1, s2);
111 }else{
112 ans = string(sz+1, '0');
113 ans[0] = ans[ans.size()-1] = '1';
114 }
115 }else{
116 string s1 = ans;
117 s1[sz>>1] = n[sz>>1] - 1;
118
119 string s2 = string(sz-1, '9');
120 // cout << s1 << " v.s. " << s2 << endl;
121 ans = choose(s1, s2);
122 }
123 }else{
124 // cout << "sz even" << endl;
125 if(n[sz>>1] == '0'){
126 // cout << "middle 0" << endl;
127 string s1 = n;
128 s1[(sz>>1)-1] = s1[sz>>1] = n[sz>>1] + 1;
129
130 string s2 = n;
131 s2[(sz>>1)-1] = s2[sz>>1] = '9';
132 int mid = sz>>1;
133 int shift = 1;
134 while((sz>>1)-1-shift >= 0 && s2[(sz>>1)-1-shift] == '0'){
135 s2[(sz>>1)-1-shift] = s2[(sz>>1)+shift] = '9';
136 ++shift;
137 }
138 if((sz>>1)-1-shift >= 0){
139 s2[(sz>>1)-1-shift] = s2[(sz>>1)+shift] = n[(sz>>1)+shift]-1;
140 // cout << s1 << " v.s. " << s2 << endl;
141 ans = choose(s1, s2);
142 }else{
143 ans = "-1";
144 }
145 }else if(n[sz>>1] == '9'){
146 // cout << "middle 9" << endl;
147 string s1 = n;
148 s1[(sz>>1)-1] = s1[sz>>1] = n[sz>>1] - 1;
149
150 string s2 = n;
151 s2[(sz>>1)-1] = s2[sz>>1] = '0';
152 int mid = sz>>1;
153 int shift = 1;
154 while((sz>>1)-1-shift >= 0 && s2[(sz>>1)-1-shift] == '9'){
155 s2[(sz>>1)-1-shift] = s2[(sz>>1)+shift] = '0';
156 ++shift;
157 }
158 if((sz>>1)-1-shift >= 0){
159 s2[(sz>>1)-1-shift] = s2[(sz>>1)+shift] = n[(sz>>1)+shift]+1;
160 // cout << s1 << " v.s. " << s2 << endl;
161 ans = choose(s1, s2);
162 }else{
163 ans = string(sz+1, '0');
164 ans[0] = ans[ans.size()-1] = '1';
165 }
166 }else{
167 // cout << "middle not 0" << endl;
168 string s1 = ans;
169 s1[(sz>>1)-1] = s1[sz>>1] = n[sz>>1] - 1;
170
171 string s2 = string(sz-1, '9');
172 // cout << s1 << " v.s. " << s2 << endl;
173 ans = choose(s1, s2);
174 }
175 }
176 }
177
178 return ans;
179 }
180};
181
182//https://leetcode.com/problems/find-the-closest-palindrome/discuss/102391/Python-Simple-with-Explanation
183//Runtime: 8 ms, faster than 16.56% of C++ online submissions for Find the Closest Palindrome.
184//Memory Usage: 6.2 MB, less than 71.34% of C++ online submissions for Find the Closest Palindrome.
185class Solution {
186public:
187 string nearestPalindromic(string n) {
188 int l = n.size();
189
190 unordered_set<string> cands;
191 cands.insert("1" + string(l-1, '0') + "1"); //999->1001, one more digit
192 if(l-1 > 0) cands.insert(string(l-1, '9')); //1001->999, one less digit
193
194 /*
195 If the final answer has the same number of digits as the input string S, then the answer must be the middle digits + (-1, 0, or 1) flipped into a palindrome.
196 0: 12345 -> 12321
197 -1: 99100 -> 99099
198 +1: 10299 -> 10300
199 */
200 string former = n.substr(0, l&1 ? (l>>1)+1 : l>>1);
201 // cout << former << endl;
202 vector<string> formers = {to_string(stoll(former)-1),
203 former,
204 to_string(stoll(former)+1)};
205
206 for(string& f : formers){
207 string later = f.substr(0, l&1 ? f.size()-1 : f.size());
208 reverse(later.begin(), later.end());
209 // cout << "insert " << f+later << endl;
210 cands.insert(f + later);
211 }
212
213 cands.erase(n);
214
215 // cout << "cands: ";
216 // for(const string& cand : cands){
217 // cout << cand << "#";
218 // }
219 // cout << endl;
220
221 return *min_element(cands.begin(), cands.end(),
222 [&n](const string& c1, const string& c2){
223 return (abs(stoll(n) - stoll(c1)) == abs(stoll(n) - stoll(c2))) ?
224 stoll(c1) < stoll(c2) :
225 (abs(stoll(n) - stoll(c1)) < abs(stoll(n) - stoll(c2)));
226 });
227 }
228};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.