最直接的想法是双“指针”法,从两端向中间扫描。但题目说的递归法,想了老半天也没想到,看了大佬的解答,原来递归法还需要借助辅助空间。

有两个trick,轻轻松松三分钟,工具函数都不用写:

  1. tolower函数
  2. isalnum函数
class Solution {
public:
    /**
     *
     * @param s string字符串
     * @return bool布尔型
     */
    bool isPalindrome(string s) {
        // write code here
        int size = s.size();
        if (size < 2) return true;
        // 仅考虑字母和数字,忽略大小写
        int i = 0, j = size - 1;
        while (i < j) {
            char a = tolower(s[i]), b = tolower(s[j]);
            if (a == b) { ++i; --j;}
            else if (!isalnum(a)) ++i;
            else if (!isalnum(b)) --j;
            else return false;
        }
        return true;
    }
};