最直接的想法是双“指针”法,从两端向中间扫描。但题目说的递归法,想了老半天也没想到,看了大佬的解答,原来递归法还需要借助辅助空间。
有两个trick,轻轻松松三分钟,工具函数都不用写:
- tolower函数
- 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; } };