Parentheses

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:
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        backtrack(res, 0, 0, "", n);
        return res;

    }

    void backtrack(vector<string>& res, int left, int right, string slu, int n) {
        if (slu.size() == n*2) {
            res.push_back(slu);
            return;
        }
        if (right > left) return;

        if (left < n) {
            backtrack(res, left + 1,  right, slu + "(", n);
        }
        if (right < left) {
            backtrack(res, left, right + 1, slu +")", n);
        }
    }
};

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.

class Solution {
public:
    int longestValidParentheses(string s) {
        int len = s.size();
        if (len < 2) return 0;
        stack<pair<char, int>> st;
        st.push({s[0], 0});
        for (int i = 1; i < s.size(); ++i) {
            if (s[i] == '(') st.push({s[i], i});
            else {
                if (st.empty() || st.top().first != '(') st.push({s[i], i});
                else st.pop();
            }
        }
        int end = len;
        int start = -1;
        int max_len  =0;
        while (!st.empty()) {
            start = st.top().second;
            st.pop();
            max_len = max(max_len, end - start - 1);
            end = start;
        }

        max_len = max(max_len, end);
        return max_len;
    }
};

241. Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

Example 1 Input: 2-1-1.

((2-1)-1) = 0
(2-(1-1)) = 2
Output: [0, 2]

Example 2 Input: 2*3-4*5

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
Output: [-34, -14, -10, -10, 10]

class Solution {
public:
    vector<int> diffWaysToCompute(string input) {
        unordered_map<string, vector<int>> memo;
        return helper(input, memo);
    }

    vector<int> helper(string input, unordered_map<string, vector<int>>& memo) {
        if (memo.find(input) != memo.end()) return memo[input];
        vector<int> res;
        bool has_operator = false;
        for (size_t i = 0; i < input.size(); ++i) {
            if (input[i] == '+' || input[i] == '-' || input[i] == '*') {
                has_operator = true;
                string left_str = input.substr(0, i);
                string right_str = input.substr(i+1);
                auto left = helper(left_str, memo);
                auto right = helper(right_str, memo);

                for (auto num1 : left) {
                    for (auto num2 : right) {
                        switch (input[i]) {
                            case '+':
                                res.push_back(num1 + num2);
                                break;
                            case '-':
                                res.push_back(num1 - num2);
                                break;
                            case '*':
                                res.push_back(num1 * num2);
                                break;
                            default:
                                break;
                        }
                    }
                }
            }
        }
        if (!has_operator) res.push_back(stoi(input));
        memo[input] = res;
        return res;
    }
};