022. Generate Parentheses

Difficulty: Medium

Frequency: 

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:

"((()))", "(()())", "(())()", "()(())", "()()()"


My solution:
Data structure:
string, recursive
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> results;
        helper(results, "", n, 0);
        return results;
    }
    void helper(vector<string> &v, string str, int n, int m) {
        if (n == 0 && m == 0) {
            v.push_back(str);
            return;
        }
        if (m > 0) {
            helper(v, str+")", n, m - 1);
        }
        if (n > 0) {
            helper(v, str+"(", n - 1, m + 1);
        }
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
Advertisements

020. Valid Parentheses

Difficulty: Easy

Frequency: N/A

 

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.


My solution:
Data structure:
stack, string
Steps:
Complexity:
Runtime: O(n)
Space: O(n)
Test cases:
Corner cases:
Code:
class Solution {
public:
    bool isValid(string s) {
        stack&lt;char&gt; myStack;
        for (int i = 0; i &lt; s.size(); i++) {
            if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
                myStack.push(s[i]);
            } else if (s[i] == ')') {
                if(myStack.empty() || myStack.top() != '(') return false;
                myStack.pop();
            } else if (s[i] == '}') {
                if(myStack.empty() || myStack.top() != '{') return false;
                myStack.pop();
            } else if (s[i] == ']') {
                if(myStack.empty() || myStack.top() != '[') return false;
                myStack.pop();
            }
        }
        return myStack.empty();
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

017. Letter Combinations of a Phone Number

Difficulty: Medium

Frequency: N/A

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.


My solution:
Data structure:
vector, string
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0) return vector<string>();
        vector<string> results;
        results.push_back("");
        unordered_map<char, string> mapping = {{'0', ""},
                                              {'1', ""},
                                              {'2', "abc"},
                                              {'3', "def"},
                                              {'4', "ghi"},
                                              {'5', "jkl"},
                                              {'6', "mno"},
                                              {'7', "pqrs"},
                                              {'8', "tuv"},
                                              {'9', "wxyz"}};

        for (int i = 0; i < digits.size(); i++) {
            string curr = mapping[digits[i]];
            if(!curr.size()) continue;
            vector<string> tmp;
            for (int j = 0; j < results.size(); j++) {
                for (int k = 0; k < curr.size(); k++) {
                    tmp.push_back(results[j] + curr[k]);
                }
            }
            results.swap(tmp);
        }
        return results;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
1. swap() is interesting.
2. Try backtracking.

010. Regular Expression Matching

Difficulty: Hard

Frequency: N/A

 

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

My solution:
Data structure:
string
Steps:
1. Check empty input
2. If the second char is not *, check the first char. Continue if they match, or it is .
3. If the second char is *, check whether the t.substr(2) matches s. If not, check whether
    p[0] == ‘.’ or p[0] == s[0].
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    bool isMatch(string s, string p) {
        if (p.empty()) return s.empty();
        if (p[1] != '*') {
            if(p[0] == s[0] || (p[0] == '.' && s[0] != '\0')) {
                return isMatch(s.substr(1), p.substr(1));
            } else {
                return false;
            }
        } else {
            if (isMatch(s, p.substr(2))) return true;
            int idx = 0;
            while (idx < s.size() && (s[idx] == p[0] || p[0] == '.')) {
                if (isMatch(s.substr(++idx), p.substr(2))) return true;
            }
            return false;
        }
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
1. Need to understand basic regular expression, like .* means zero or more any characters

012. Integer to Roman

Difficulty: Medium

Frequency: N/A

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.


My solution:
Data structure:
array, string
Steps:
Complexity:
Runtime: O(n)
Space: O(1)
Test cases:
Corner cases:
Code:
class Solution {
public:
    string intToRoman(int num) {
        array&lt;string, 4&gt; M = {&quot;&quot;, &quot;M&quot;, &quot;MM&quot;, &quot;MMM&quot;};
        array&lt;string, 10&gt; C = {&quot;&quot;, &quot;C&quot;, &quot;CC&quot;, &quot;CCC&quot;, &quot;CD&quot;, &quot;D&quot;, &quot;DC&quot;, &quot;DCC&quot;, &quot;DCCC&quot;, &quot;CM&quot;};
        array&lt;string, 10&gt; X = {&quot;&quot;, &quot;X&quot;, &quot;XX&quot;, &quot;XXX&quot;, &quot;XL&quot;, &quot;L&quot;, &quot;LX&quot;, &quot;LXX&quot;, &quot;LXXX&quot;, &quot;XC&quot;};
        array&lt;string, 10&gt; I = {&quot;&quot;, &quot;I&quot;, &quot;II&quot;, &quot;III&quot;, &quot;IV&quot;, &quot;V&quot;, &quot;VI&quot;, &quot;VII&quot;, &quot;VIII&quot;, &quot;IX&quot;};
        return M[num / 1000] + C[num % 1000 /100] + X[num % 1000 % 100 / 10] + I[num % 1000 % 100 % 10];
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

006. ZigZag Conversion

Difficulty: Easy

Frequency: N/A

 

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

 


Test Cases:

1. numRows can be 0, 1, 2, and n
2. string can be empty, 1 char, 2 char, and n char.
3. Do the combinations of 1 and 2.

Solution 1:

Data structure:
string
Steps:
1. Divide each row into cycles
2. Print 1 or 2 elements in the cycle in the row
Complexity:
Runtime: O(n) 16ms
Space: O(1)
Code:
class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        string result;
        int cycle = 2 * numRows - 2;
        for (int i = 0 ; i < numRows; i++) {
            for (int j = i; j < s.size(); j = j + cycle) {
                result.push_back(s[j]);
                int second_element = (j - i) + cycle - i;
                if (i != 0 && i != numRows - 1 && second_element < s.size())
                    result.push_back(s[second_element]);
            }
        }
        return result;
    }
};

Solution 2:

Data structure:
string, vector
steps:
1. Push the first column to numRows vectors.
2. Push the second column reversely to (numRows – 2) vectors.
Complexity:
Runtime: O(n) 40ms
Space: O(n)
Code:
class Solution {
public:
    string convert(string s, int numRows) {
        vector<string> vs(numRows, "");
        int n = s.size(), i = 0;
        while (i < n) {
            for (int j = 0; j < numRows && i < n; j++) {
                vs[j].push_back(s[i++]);
            }
            for (int j = numRows - 2; j >= 1 && i < n; j--) {
                vs[j].push_back(s[i++]);
            }
        }
        string zigzag;
        for (string s : vs) zigzag += s;
        return zigzag;
    }
};


Submission errors:

 

Things to learn:

1. Solution 1 is faster, but the calculation for the second element is not straightforward.

2. Solution 2 is slower, but quite easy to understand.