[数据结构与算法]LeetCode - 解题笔记 - 125 - Valid Palindrome

Solution 1

判断回文字符串本身没有什么难度，麻烦的就是根据语言选择对应的字符串处理API，必要时自行实现：剔除非字母-数字字符以及全小写。

对于C语言，有两个可用的函数：

isalnum ：判断当前字符是否为字母-数字字符

tolower ：转对应小写字符（如存在）

本题一开始我先处理成一个无其他字符并转小写的字符串再处理，后来整理题解的时候反应过来其实可以直接在原始字符串上做，节省了一个字符串的空间占用

• 时间复杂度：$O(N)$，其中$N$为输入字符串的长度，完整遍历一次
• 空间复杂度：$O(1)$，仅维护常数个状态值

class Solution {
public:
    bool isPalindrome(string s) {
        if (s.size() == 0) { return true; }
        
        int left = 0, right = s.size() - 1;
        while (left < right) {
            // 从首尾找到下一个字母-数字字符
            while (left < right && !isalnum(s[left])) { left++; }
            while (left < right && !isalnum(s[right])) { right--; }
            
            if (left < right) {
                // cout << s[left] << " " << s[right] << endl;
                if (tolower(s[left]) != tolower(s[right])) { return false; }
                
                left++;
                right--;
            }
        }
        
        return true;
    }
};

Solution 2

Solution 1的Python实现

在Python，对应的API名称相同，但是为str的自有方法

class Solution:
    def isPalindrome(self, s: str) -> bool:
        if len(s) == 0: return True
        
        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 left < right:
                if s[left].lower() != s[right].lower(): return False
                
                left += 1
                right -= 1
        
        return True