20. Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

S: stack

可以不用hashtable，直接用switch语句枚举可能的情况

    bool isValid(string s) {
        stack<char> left;
        unordered_map<char, char> par;
        par['('] = ')'; 
        par['{'] = '}';
        par['['] = ']';
        for(auto i: s){
            if(par.find(i) != par.end()) left.push(i);
            else if(left.empty() || par[left.top()] != i) return false;
            else left.pop();
        }
        return left.empty();
    }

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
Show Company Tags
Show Tags
Show Similar Problems

S: recursion

记录可用的左右括号数，递归

class Solution {
public:
    vector<string> result;
    vector<string> generateParenthesis(int n) {
        parHelp(0, n, "");
        return result;
    }
    void parHelp(int right, int left, string s){//left: count how many left par can be use; right 
        if(right == 0 && left == 0) result.push_back(s);
        if(left > 0) parHelp(right+1, left-1, s+'(');
        if(right > 0) parHelp(right-1, left, s+')');
    }
};

32. Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

Show Tags
Show Similar Problems

S: stack

用stack记录invalid字符的index,每次在i处形成一个pair,计算从i到上一个invalid index的长度即为valid parentheses的长度。

这里有个trick是初始stack第一个值为-1，这样可以避免stack为空的判断，并且在valid parentheses从0开始时也能正确得到长度。

    int longestValidParentheses(string s) {
        int n = s.size(), maxL = 0;
        stack<int> invalidIdx;
        //a trick to avoid empty stack and useful
        //to calculate length when valid substring start at 0
        invalidIdx.push(-1); 
        for(int i = 0; i < n; ++i){
            int idx = invalidIdx.top();
            if(idx != -1 && s[idx] == '(' && s[i] == ')'){ 
                invalidIdx.pop();//这里是从上一个invalid index算，要先pop再取top
                maxL = max(maxL, i-invalidIdx.top());
            }
            else invalidIdx.push(i);
        }
        return maxL;
    }

301. Remove Invalid Parentheses

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses(and).

Examples:

"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

S: DFS

用count记录左右括号出现次数，若右括号多于左括号则删除一右括号保证到目前为止valid，进入下一层循环。

startPos表示startPost之前都是valid，delPos记录上次删除右括号的坐标加一，这次删除只能在delPos之后进行。

对于左括号多于右括号的情况，将s翻转再进行bfs即可

class Solution {
public:
    vector<string> removeInvalidParentheses(string s) {
        par.resize(2);
        par[0] = ')';
        par[1] = '(';
        dfs(s, 0, 0, 0);
        return result;
    }

    void dfs(string s, int startPos, int delPos, int rev) {
        for (int count = 0, i = startPos; i < s.size(); ++i) {
            if (s[i] == par[rev]) {
                count++;
            } else if (s[i] == par[1 - rev]) {
                count--;
            } 
            if (count > 0) {
                for (int j = delPos; j <= i; ++j) {
                    if (s[j] == par[rev] && (j == delPos || s[j - 1] != par[rev])) {
                        string sj = s.substr(0, j) + s.substr(j + 1);
                        dfs(sj, i, j, rev);
                    }
                }
                return;  //此s不valid直接返回
            }
        }

        reverse(s.begin(), s.end());
        if (rev == 0) {  //没有反向检查过，进行反向dfs
            dfs(s, 0, 0, 1);
        } else {  //已经反向检查过，push结果
            result.push_back(s);
        } 
    }

private:
    vector<char> par;
    vector<string> result;
};

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"isnota 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.

class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            if (!isAlpha(s[left])) {
                left++;
            } else if (!isAlpha(s[right])) {
                right--;
            } else {
                if (tolower(s[left]) == tolower(s[right])) {
                    left++;
                    right--;
                } else {
                    return false;
                }
            }
        }
        return true;
    }

private: 
    bool isAlpha(char a) {
        return (a >= 'a' && a <= 'z') || (a >= 'A' && a <= 'Z') || (a >= '0' && a <= '9');
    }
};