C++ 0125.cpp
class Solution {
public:
bool isPalindrome(string s) {
string p;
for (auto c : s)
{
if (c >= 'A' && c <= 'Z')
p += c - 'A' + 'a';
if (c >= 'a' && c <= 'z')
p += c;
if (c >= '0' && c <= '9')
p += c;
}
string r = p;
reverse(r.begin(), r.end());
return p == r;
}
};
Difficulty
and has an acceptance rate of about 54% (10+ million submissions).
Typical patterns to solve this problem:
- String
- Two Pointers
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation defines a method that determines whether an input string reads the same forward and backward when case differences and non-alphanumeric characters are ignored. It first creates a normalized version of the input containing only lower-case letters and digits, then generates a reversed copy of that normalized string, and finally compares the two for equality.
Key Steps
The first phase iterates over each character of the original string and selectively appends characters that belong to the alphanumeric set. Upper-case letters are converted to lower-case before being added.
string p;
for (auto c : s)
{
if (c >= 'A' && c <= 'Z')
p += c - 'A' + 'a';
if (c >= 'a' && c <= 'z')
p += c;
if (c >= '0' && c <= '9')
p += c;
}
After the normalized string p is built, a second string r is created as a copy of p. The standard library function reverse is then applied to reorder the characters in place, producing the mirror image of the filtered input.
string r = p;
reverse(r.begin(), r.end());
The final step performs a direct equality check between the normalized string and its reversed counterpart. The boolean result of this comparison is returned to the caller.
return p == r;
Edge Cases Handled
When the input consists solely of characters that are filtered out-such as punctuation, whitespace, or symbols-the normalization loop produces an empty string. The reversal of an empty string yields another empty string, and the equality comparison correctly returns true, treating the input as a palindrome under the defined criteria.
If the input is an empty string from the start, the same logic applies, and the method returns true.
Numeric characters are preserved without transformation, allowing strings that contain only digits or a mixture of digits and letters to be evaluated correctly.
Case insensitivity is achieved by converting any uppercase alphabetic character to its lowercase counterpart before inclusion, ensuring that strings differing only by letter case are considered equivalent.
Performance Optimizations
The algorithm constructs the filtered representation in a single pass, avoiding multiple traversals of the original data. By appending directly to the result string p, it eliminates the need for intermediate containers or additional copying during the filtering stage.
Creating a separate copy r only once and then applying reverse in place leverages the highly optimized standard library implementation, which typically operates with minimal overhead.
The final equality check uses the built-in operator== for std::string, which can quickly compare lengths before performing a character-by-character comparison, allowing early exit when a mismatch is detected.
Overall, the method balances clarity with efficient use of standard library facilities, resulting in a straightforward yet performant solution for palindrome verification under the specified constraints.
ELI5 - Simplified Explanation
Imagine holding a magic crayon that draws a line of letters and numbers. Sometimes people leave messy scribbles like spaces, dots, or exclamation marks between the letters. This code starts by looking at a line of characters one by one. It decides to keep only the letters and the numbers, while letting all those messy extra marks just disappear. Every time it finds a letter that is big and uppercase, it turns it into a small, friendly lowercase version so that everything looks the same. After cleaning up all the characters and putting them in a new, tidy line, it makes a secret mirror copy of that line. It then flips the mirror copy around so the last character becomes the first one. Finally, it holds the original clean line next to the flipped one to check if they look exactly the same from both directions, just like the word kayak or the numbers in 121. If they match perfectly, it means the group is a palindrome.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| author | solutions | ||||||||||||
| www | AlgoMonster | C++ | Python | Java | TS | ||||||||
| WalkCCC | C++ | Python | Java | ||||||||||
| leetcode.ca | C++ | Python | C# | Java | Rust | JS | Go | PHP | TS | ||||
| LeetcodeHelp | C++ | Python | Java | ||||||||||
| MemoryLimitExceeded | C++ | Python | |||||||||||
| Progiez | C++ | Python | Java | ||||||||||
| github | AdelDaniel | Dart | |||||||||||
| aylei | Rust | ||||||||||||
| begeekmyfriend | C | ||||||||||||
| BigEggStudy | C# | ||||||||||||
| black-shadows | C++ | ||||||||||||
| bujosa | Python | ||||||||||||
| chandansgowda | Python | ||||||||||||
| charles-wangkai | Java | ||||||||||||
| chenyanzhe | C++ | ||||||||||||
| DimitrisJim | C | ||||||||||||
| everthis | JS | ||||||||||||
| fartem | Ruby | ||||||||||||
| FelixFan1122 | C# | ||||||||||||
| fengvyi | C++ | ||||||||||||
| fpdjsns | C++ | ||||||||||||
| gaosq0604 | Python | ||||||||||||
| Garvit244 | Python | ||||||||||||
| gouthampradhan | Java | ||||||||||||
| halfrost | Go | ||||||||||||
| haoel | C++ | ||||||||||||
| JoshCrozier | JS | ||||||||||||
| keineahnung2345 | C++ | ||||||||||||
| Krazune | C++ | ||||||||||||
| lennylxx | C | ||||||||||||
| linouk23 | C++ | ||||||||||||
| lkwq007 | Python | ||||||||||||
| luangong | C++ | ||||||||||||
| MacJim | C++ | ||||||||||||
| muhammadfarhankt | Go | ||||||||||||
| pruthvikp | Python | ||||||||||||
| qiyuangong | Python | ||||||||||||
| ruoru | Rust | ||||||||||||
| shreymehul | C# | ||||||||||||
| sonugiri1043 | C++ | ||||||||||||
| suxrobGM | C# | ||||||||||||
| trung-hn | Python | ||||||||||||
| varunu28 | Java | ||||||||||||
| vli02 | C | ||||||||||||
| XiaotaoGuo | C++ | ||||||||||||
| YuriSpiridonov | Python | ||||||||||||
| zfang399 | C++ | ||||||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||||||
| WalkCCC | C++, Python, Java | ||||||||||||
| leetcode.ca | C++, C#, Go, Java, JavaScript, PHP, Python, Rust, TypeScript | ||||||||||||
| LeetcodeHelp | C++, Java, Python | ||||||||||||
| MemoryLimitExceeded | Python, C++ | ||||||||||||
| Progiez | C++, Java, Python | ||||||||||||
| AdelDaniel | Dart | ||||||||||||
| aylei | Rust | ||||||||||||
| begeekmyfriend | C | ||||||||||||
| BigEggStudy | C# | ||||||||||||
| black-shadows | C++, C++ | ||||||||||||
| bujosa | Python | ||||||||||||
| chandansgowda | Python | ||||||||||||
| charles-wangkai | Java | ||||||||||||
| chenyanzhe | C++ | ||||||||||||
| DimitrisJim | C | ||||||||||||
| everthis | JavaScript | ||||||||||||
| fartem | Ruby | ||||||||||||
| FelixFan1122 | C# | ||||||||||||
| fengvyi | C++ | ||||||||||||
| fpdjsns | C++ | ||||||||||||
| gaosq0604 | Python | ||||||||||||
| Garvit244 | Python | ||||||||||||
| gouthampradhan | Java | ||||||||||||
| halfrost | Go | ||||||||||||
| haoel | C++ | ||||||||||||
| JoshCrozier | JavaScript | ||||||||||||
| keineahnung2345 | C++ | ||||||||||||
| Krazune | C++ | ||||||||||||
| lennylxx | C | ||||||||||||
| linouk23 | C++ | ||||||||||||
| lkwq007 | Python | ||||||||||||
| luangong | C++ | ||||||||||||
| MacJim | C++ | ||||||||||||
| muhammadfarhankt | Go | ||||||||||||
| pruthvikp | Python | ||||||||||||
| qiyuangong | Python | ||||||||||||
| ruoru | Rust | ||||||||||||
| shreymehul | C# | ||||||||||||
| sonugiri1043 | C++ | ||||||||||||
| suxrobGM | C# | ||||||||||||
| trung-hn | Python | ||||||||||||
| varunu28 | Java | ||||||||||||
| vli02 | C | ||||||||||||
| XiaotaoGuo | C++ | ||||||||||||
| YuriSpiridonov | Python | ||||||||||||
| zfang399 | C++ |
Videos
Similar Problems
- problem 680: Valid Palindrome II
- problem 2108: Find First Palindromic String in the Array
- problem 3035: Maximum Palindromes After Operations
Solved On The Same Day
- problem 191: Number of 1 Bits
- problem 202: Happy Number
- problem 217: Contains Duplicate
- problem 219: Contains Duplicate II
- problem 290: Word Pattern
- problem 383: Ransom Note
- problem 392: Is Subsequence
- problem 1047: Remove All Adjacent Duplicates In String
- problem 1089: Duplicate Zeros
- problem 151: Reverse Words in a String
- problem 187: Repeated DNA Sequences
- problem 51: N-Queens
- problem 52: N-Queens II
- problem 60: Permutation Sequence
- problem 68: Text Justification
- problem 76: Minimum Window Substring
- problem 135: Candy
- problem 140: Word Break II
- problem 220: Contains Duplicate III
- problem 239: Sliding Window Maximum
- problem 352: Data Stream as Disjoint Intervals
- problem 502: IPO
- problem 895: Maximum Frequency Stack
- problem 982: Triples with Bitwise AND Equal To Zero
- problem 995: Minimum Number of K Consecutive Bit Flips
- problem 996: Number of Squareful Arrays
- problem 2136: Earliest Possible Day of Full Bloom
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality