[LeetCode] Valid Palindrome

Link : 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. Note: Have you consider that the string might be empty? This is a good question to ask during an interview. For the purpose of this problem, we define empty string as valid palindrome.

Analysis:
1. determine whether a char is alphanumeric
2. jump those that are not alphnumeric
3. pointer to point to char to be compared on left side and right side
4. compare whether they are 'equal'

Code says!

Using Stack

 class class class Solution {
    public:
    int longestValidParentheses(std::string s) {
        if(s.size()<=1)
        return 0;
        int n = s.size();
        std::stack<int> stack;
        int max = 0;
        int i = -1;
        int last_invalid=-1;
        while(++i<n)
        {
            char c = s[i];
            if(c=='(')
            stack.push(i);
            else
            {
                // if there is '(' and '(' is to the right of last wrong ')'
                if(stack.size()!=0)
                {
                    int left = stack.top();
                    stack.pop();
                    if(stack.size()!=0)
                    max = max > i-stack.top() ? max : i-stack.top();
                    else
                    max = max > i - last_invalid ? max : i - last_invalid;
                }
                else// (stack.size()==0)
                last_invalid = i;
            }
        }
        return max;
    }
};

Using Dynamic Programming

 class class Solution2 {
    public:
    int longestValidParentheses(std::string s) {
        if(s.size()<=1) return 0;
        int n = s.size();
        // left stores the paired '(' for each ')'
        std::vector<int> left(s.size(),-1);
        for(int i=0; i<n; i++)
        {   //'(' or // no left char or // left index indicate invalid
            if(s[i]!=')'||i-1<0)
            continue;
            if(s[i-1] == '(') // directly paired '()'
            left[i]=i-1;
            if(s[i-1] == ')') // need to handle '(())'
            {
                int leftleft = left[i-1]-1;
                if(leftleft>=0 && s[leftleft]=='(')
                left[i] = leftleft;
            }
            if(left[i]>=0) // need to handle '()()'
            {
                int pre_right = left[i]-1;
                if(pre_right>=0&&left[pre_right]>=0)
                left[i] = left[pre_right];
            }
        }
        int max=0;
        for(int i=0; i<n; i++)
        {
            if(left[i]>=0 && i-left[i]+1>max)
            max = i-left[i]+1;
        }
        return max;
    }
};