Leetcode 125: Valid Palindrome

Leetcode 125: valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

永远会记得这题，这题是面qualtrics时的原题，我记得我当时还没有做到这一题，或者很早之前做的完全没有印象，当时拿到这个题目的时候，首先想到的方法是先对 输入的数据进行预处理，使其变成只有a-z的string，我记得当时面试官说你这样就对原来的input进行了修改，我当时没有明白过来是什么意思，不对input修改怎么做，后来面试过后再想了想发现原来是可以直接在递归的时候单独对每个char进行处理，这样整个字符串就只用scan一遍就可以了，如果预处理的话，需要scan 两遍啊！！！！！我太笨了！
这个题目，对于不需要考虑的特殊字符可以直接跳过，那么怎么判断一个字符合不合法呢？ 如果这个字符是0-9、a-z/A-Z之间就是合法的，然后对于合法的字符需要统一到小写或者大写字符上面去。 可以用一个isValid函数来进行判断。

在leetcode上面，用recursion对palindrome进行判断，能通过小集合不能通过大集合， 出现runtime error。 一开始对出现这个问题不能理解，因为不能发现时间复杂度有什么区别，也不能进一步优化了，后来才知道原来一般的recursion对空间复杂度都是有要求的，如果输入的数据太大，会很消耗stack上面的空间，这样也能导致程序出现问题，但是如果用iteration代替recursion，就能消除对空间复杂度上的依赖。

所以，对于recursion 和iteration都能解决的题目，如果recursion 和iteration 写起来其实难度相当，那么优先选用iteration来做。 这样能节省空间。

class Solution {
private:
    bool isValid(string &s, int i) {
        if (isdigit(s[i]) || isalpha(s[i])) {
            if (s[i] <= 'Z' && s[i] >= 'A')s[i] = tolower(s[i]);
            return true;
        }else {
            return false;
        }
    }
public:
    bool isPalindrome(string s) {
        //sanity check
        if (s.size() == 0) return true;
        int start = 0;
        int end = s.size()-1;
        while (start < end) {
            if (!isValid(s, start)) {
                start++;
            }else if (!isValid(s, end)) {
                end--;
            }else if (s[start] == s[end]) {
                start++;
                end--;
            }else return false;
        }
        return true;
    }
};