How do I check if a string is a valid palindrome?

You can check if a string is a valid palindrome by comparing characters from both ends using two pointers, skipping non-alphanumeric characters and ensuring case-insensitivity.

What is the time complexity of solving the Valid Palindrome problem?

The time complexity is O(n), where n is the length of the string, as we traverse the string once with two pointers.

What are some common mistakes when solving the Valid Palindrome problem?

Some common mistakes include not properly skipping non-alphanumeric characters, failing to convert characters to lowercase, and not handling edge cases like empty strings.

How do I handle non-alphanumeric characters in the Valid Palindrome problem?

Non-alphanumeric characters should be skipped during the comparison by checking each character and moving the pointers accordingly.

Can you explain the two-pointer technique for Valid Palindrome?

The two-pointer technique involves setting one pointer at the beginning and the other at the end of the string, comparing characters and moving towards the center, skipping non-alphanumeric characters and handling case insensitivity.

#125

Easy

auto_awesome双·指针·invariant

LeetCode 题解工作台

验证回文串

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个回文串。字母和数字都属于字母数字字符。给你一个字符串 s ，如果它是回文串，返回 true ；否则，返回 false 。示例 1：输入: s = "A man, a pl…

双指针字符串

题目描述

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

示例 1：

输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。

示例 2：

输入：s = "race a car"
输出：false
解释："raceacar" 不是回文串。

示例 3：

输入：s = " "
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。
由于空字符串正着反着读都一样，所以是回文串。

提示：

1 <= s.length <= 2 * 10⁵
s 仅由可打印的 ASCII 字符组成

lightbulb

解题思路

方法一：双指针

我们用双指针 $i$ 和 $j$ 分别指向字符串 $s$ 的两端，接下来循环以下过程，直至 $i \geq j$ ：

如果 $s[i]$ 不是字母或数字，指针 $i$ 右移一位，继续下一次循环；
如果 $s[j]$ 不是字母或数字，指针 $j$ 左移一位，继续下一次循环；
如果 $s[i]$ 和 $s[j]$ 的小写形式不相等，返回 false；
否则，指针 $i$ 右移一位，指针 $j$ 左移一位，继续下一次循环。

循环结束，返回 true。

时间复杂度 $O(n)$ ，其中 $n$ 是字符串 $s$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def isPalindrome(self, s: str) -> bool:
        i, j = 0, len(s) - 1
        while i < j:
            if not s[i].isalnum():
                i += 1
            elif not s[j].isalnum():
                j -= 1
            elif s[i].lower() != s[j].lower():
                return False
            else:
                i, j = i + 1, j - 1
        return True

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Evaluate the candidate’s ability to implement two-pointer techniques.
question_mark
Check if the candidate effectively handles edge cases such as empty strings or strings with non-alphanumeric characters.
question_mark
Observe the candidate's ability to optimize both time and space for this problem.

warning

常见陷阱

外企场景

error
Forgetting to ignore non-alphanumeric characters, which can lead to incorrect results.
error
Not converting all characters to lowercase, causing mismatches between uppercase and lowercase letters.
error
Not handling the empty string or edge cases where the string is very short.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Palindromes with mixed case and special characters.
arrow_right_alt
Strings with a large number of non-alphanumeric characters.
arrow_right_alt
Edge case handling for strings of length 1 or 0.

help

常见问题

外企场景

继续练习

#151 反转字符串中的单词 #165 比较版本号 #28 找出字符串中第一个匹配项的下标