LeetCode: 125 Valid Palindrome

Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Example:

Input: "A man, a plan, a canal: Panama"
Output: true

Input: "race a car"
Output: false

问题

给定一个字符串 s，判断它是否是一个回文字符串，仅考虑字母数字字符并忽略大小写。

解决方案 1

双指针法

Approach 1 / 方法 1

使用双指针从字符串的两端向中间移动，忽略非字母数字字符，并比较字母数字字符是否相等。

Detailed Steps / 详细步骤

Initialization / 初始化:

1. Convert the string to lowercase and initialize two pointers: one at the start and one at the end of the string.
   将字符串转换为小写并初始化两个指针：一个在字符串的起始位置，一个在字符串的末尾。

Step 1 / 第一步:

2. Move the left pointer to the right until it points to an alphanumeric character.
   将左指针向右移动，直到它指向一个字母数字字符。

Step 2 / 第二步:

3. Move the right pointer to the left until it points to an alphanumeric character.
   将右指针向左移动，直到它指向一个字母数字字符。

Step 3 / 第三步:

4. Compare the characters at the left and right pointers. If they are not equal, return false.
   比较左指针和右指针的字符。如果它们不相等，返回 false。

Step 4 / 第四步:

5. Move both pointers towards the center and repeat steps 2-4 until the pointers meet or cross each other.
   将两个指针向中间移动，重复步骤 2-4，直到指针相遇或交叉。

Implementation / 实现

python

def isPalindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

Explanation / 解释

1. Step 1 / 第一步:

• Convert the string to lowercase and initialize two pointers.
  将字符串转换为小写并初始化两个指针。

2. Step 2 / 第二步:

• Move the left pointer to the next alphanumeric character.
  将左指针移动到下一个字母数字字符。

3. Step 3 / 第三步:

• Move the right pointer to the previous alphanumeric character.
  将右指针移动到前一个字母数字字符。

4. Step 4 / 第四步:

• Compare characters at the left and right pointers.
  比较左指针和右指针的字符。

5. Step 5 / 第五步:

• Move both pointers towards the center and repeat until they meet or cross.
  将两个指针向中间移动并重复，直到它们相遇或交叉。

Complexity Analysis / 复杂度分析

• Time Complexity: O(n), where n is the length of the string
  时间复杂度: O(n)，其中 n 是字符串的长度

• Space Complexity: O(1), no additional space required
  空间复杂度: O(1)，不需要额外空间

Key Concept / 关键概念

• Using two pointers to compare characters from both ends of the string
  使用双指针从字符串的两端比较字符

解决方案 2

清理字符串后比较

Approach 2 / 方法 2

将字符串中所有的非字母数字字符去除，并转换为小写，然后比较处理后的字符串是否等于其反转后的字符串。

Detailed Steps / 详细步骤

Initialization / 初始化:

1. Use a generator expression to filter out non-alphanumeric characters and convert the string to lowercase.
   使用生成器表达式去除非字母数字字符并将字符串转换为小写。

Step 1 / 第一步:

2. Join the filtered characters into a new string.
   将过滤后的字符连接成一个新的字符串。

Step 2 / 第二步:

3. Compare the new string with its reverse.
   比较新字符串和它的反转字符串。

Implementation / 实现

python

def isPalindrome(s: str) -> bool:
    filtered_chars = ''.join(char.lower() for char in s if char.isalnum())
    return filtered_chars == filtered_chars[::-1]

Explanation / 解释

1. Step 1 / 第一步:

• Filter out non-alphanumeric characters and convert to lowercase.
  过滤掉非字母数字字符并转换为小写。

2. Step 2 / 第二步:

• Join the filtered characters into a new string.
  将过滤后的字符连接成一个新的字符串。

3. Step 3 / 第三步:

• Compare the new string with its reverse.
  比较新字符串和它的反转字符串。

Complexity Analysis / 复杂度分析

• Time Complexity: O(n), where n is the length of the string
  时间复杂度: O(n)，其中 n 是字符串的长度

• Space Complexity: O(n), due to the space required for the filtered string
  空间复杂度: O(n)，因为需要空间存储过滤后的字符串

Key Concept / 关键概念

• Filtering and comparing the processed string with its reverse
  过滤并比较处理后的字符串与其反转字符串

Tips / 提示

• For very long strings, the two-pointer method may be more space-efficient.
  对于非常长的字符串，双指针方法可能更节省空间。

Solution Template for similar questions / 提示

• Use two-pointer technique or preprocess the string to remove non-alphanumeric characters.
  使用双指针技术或预处理字符串以去除非字母数字字符。

What does the main algorithm of this question aim to test? / 这个问题的主要算法旨在测试什么？

Understanding of string manipulation and two-pointer techniques
理解字符串操作和双指针技术

5 more similar questions / 推荐5问题

1. LeetCode 680. Valid Palindrome II
2. LeetCode 234. Palindrome Linked List
3. LeetCode 9. Palindrome Number
4. LeetCode 266. Palindrome Permutation
5. LeetCode 131. Palindrome Partitioning

More

• LeetCode Discuss
• LeetCode Explore
• GeeksforGeeks
• Stack Overflow

Recommended Resources:

LeetCode #125: Valid Palindrome | Beginner’s Programming Interview by Algo Engine
[https://www.youtube.com/watch?v=4rzENqwlVU8]