# 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:

# 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.