Problem 125

Abstract / Summary

Check if a string reads the same forwards and backwards ignoring spaces punctuation and capitalization

Note

The full problem description, including helpful examples, can be found on LeetCode.

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;
    }
};
22 lines | 437 bytes | submitted August 9, 2023 | GitHub   tab size 4

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 54% (10+ million submissions).

Typical patterns to solve this problem:
  • String
  • Two Pointers
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 6 | μ = 6.52 | σ = 0.92

Complexity Analysis

Time: linear
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
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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++
65 links | 47 authors | 12 languages

Videos

These are a few popular YouTube videos for this problem:
YouTube video 'Valid Palindrome - Leetcode 125 - Python'
NeetCode 15 mins
Valid Palindrome - Leetcode 125 - Python
YouTube video 'Valid Palindrome - Leetcode 125 - 2 Pointers (Python)'
Greg Hogg 6 mins
Valid Palindrome - Leetcode 125 - 2 Pointers (Python)
YouTube video '125. Valid Palindrome || Java || Leetcode || Hindi'
Coding Sphere 8 mins
125. Valid Palindrome || Java || Leetcode || Hindi
YouTube video 'Leetcode | 125. Valid Palindrome | Easy | Java Solution'
Developer Docs 7 mins
Leetcode | 125. Valid Palindrome | Easy | Java Solution
YouTube video 'Valid Palindrome || Leetcode 125 || 1 Variant Question Big Tech Actually Asks'
Coding with Minmer 13 mins
Valid Palindrome || Leetcode 125 || 1 Variant Question Big Tech Actually Asks
YouTube video 'LeetCode 125: Valid Palindrome | Beginner's Programming Interview'
Algo Engine 7 mins
LeetCode 125: Valid Palindrome | Beginner's Programming Interview
YouTube video 'Valid Palindrome - LeetCode 125 - JavaScript'
AlgoJS 6 mins
Valid Palindrome - LeetCode 125 - JavaScript
YouTube video 'Valid Palindrome | Leet code 125 | Theory explained + Python code | August Leet code challenge'
Sai Anish Malla 9 mins
Valid Palindrome | Leet code 125 | Theory explained + Python code | August Leet code challenge
YouTube video 'Valid Palindrome - LeetCode 125 - Coding Interview Questions'
One Code Man 7 mins
Valid Palindrome - LeetCode 125 - Coding Interview Questions
YouTube video 'Valid Palindrome | Day 3 | 2 Pointer & Reverse [ August LeetCoding Challenge ] [ Leetcode #125 ]'
Algorithms Made Easy 4 mins
Valid Palindrome | Day 3 | 2 Pointer & Reverse [ August LeetCoding Challenge ] [ Leetcode #125 ]
YouTube video 'Valid Palindrome - LeetCode 125 | Two Pointers | Full Concept + Python Code'
DKodeTree 7 mins
Valid Palindrome - LeetCode 125 | Two Pointers | Full Concept + Python Code
YouTube video 'LeetCode 125. Valid Palindrome - Interview Prep Ep 134'
Fisher Coder 10 mins
LeetCode 125. Valid Palindrome - Interview Prep Ep 134
YouTube video 'LeetCode 125 - Valid Palindrome - C++'
iamdriy 6 mins
LeetCode 125 - Valid Palindrome - C++
YouTube video 'valid palindrome leetcode | leetcode 125 | two solution | regex | Facebook'
Naresh Gupta 9 mins
valid palindrome leetcode | leetcode 125 | two solution | regex | Facebook
YouTube video '125. Valid Palindrome || NEETCODE 150'
TechWithSaumya 8 mins
125. Valid Palindrome || NEETCODE 150
YouTube video '125. Valid Palindrome | JavaScript | LeetCode | Blind 75'
LeetCodeWithMonu 11 mins
125. Valid Palindrome | JavaScript | LeetCode | Blind 75
YouTube video '125. Valid Palindrome |  LEETCODE Top Interview Questions | LEETCODE EASY'
code Explainer 3 mins
125. Valid Palindrome | LEETCODE Top Interview Questions | LEETCODE EASY
YouTube video 'Valid Palindrome | Leetcode 125 | Recursion Approach | Python Telugu | srkcodes'
Srk Codes 8 mins
Valid Palindrome | Leetcode 125 | Recursion Approach | Python Telugu | srkcodes
YouTube video 'Can You Detect a Palindrome? (LeetCode 125: Valid Palindrome)'
Code With Zi 7 mins
Can You Detect a Palindrome? (LeetCode 125: Valid Palindrome)
YouTube video 'LeetCode 125: Valid Palindrome | C# Solution | Two Pointer Approach |'
Code Scribbler 7 mins
LeetCode 125: Valid Palindrome | C# Solution | Two Pointer Approach |
20 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

3 similar problems

Solved On The Same Day

9 easy 2 medium 16 hard
28 solutions   August 9, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • 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