# 125-Palindrome check
###### tags: `Easy`
## Question
https://leetcode.com/problems/valid-palindrome/

## Solution
1. 篩掉標點符號
2. 轉換大小寫
3. 比較(two pointer)
### C++

class Solution {
public:
bool isValid(char ch)
    {
        if(ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z' || ch >= '0' && ch <= '9')
            return 1;
        else
            return 0;
    }
    
    char toLowerCase(char ch)
    {
        if(ch >= 'a' && ch <= 'z' || ch >= '0' && ch <= '9')
            return ch;
        else
            return ch - 'A' + 'a';
    }
    
    bool checkPalindrom(string temp)
    {
        int st = 0;
        int e = temp.size() - 1;
        while(st < e)
        {
            if(temp[st] != temp[e])
                return 0;
            else
            {
                st++;
                e--;
            }
        }
        return 1;
    }
    
    bool isPalindrome(string s) {
        string temp = "";
        for(int i = 0; i < s.size(); i++)
        {
            if(isValid(s[i]))
                temp.push_back(s[i]);
        }
        for(int j = 0; j < temp.size(); j++)
        {
            temp[j] = toLowerCase(temp[j]);
        }
        return checkPalindrom(temp);
    }
};

### Python
想法主要兩種：
1. 另外創一個反向的做對比, 故都O(N) space
實作一：用string
*但string一般immutable，作 str+= "???" 等於重新loop一次舊string，故 Ｏ(N^2) time
實作二：用vector char []
動態數組直接append, O(N) time

2. 直接頭尾比對，O(N) time
實作一：用遞迴，注意遞迴產生call stack，故O(N) space
實作二：直接迴圈，O(1) space