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.
Solution
Just use a stack, push when empty, or left parenthese found; pop when found a match.
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.
// record the position of first left parenthesis as start
start=i+1;
}
else{
stack.pop();
// if stack is empty means all valid pairs are gone,current whole length i-start+1 is longest
if (stack.isEmpty()){
maxLen=Math.max(i-start+1, maxLen);
}
else{
// if stack is not empty, then for current i the longest valid parenthesis length is i-stack.peek()
maxLen=Math.max(i-stack.peek(),maxLen);
}
}
}
}
return maxLen;
}
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: “((()))”, “(()())”, “(())()”, “()(())”, “()()()”
DFS + Backtracking Solution
left/right represents how many l/r brackets left for use
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public ArrayList<String> generateParenthesis(int n) {
ArrayList<String> res = new ArrayList<String>();
StringBuilder sb = new StringBuilder();
if(n==0) return res;
dfs(res, sb, n, n);
return res;
}
privatevoiddfs(ArrayList<String> res, StringBuilder sb,int left, int right){
if(left > right) return;
if(left == 0 && right == 0){
res.add(sb.toString());
return;
}
if(left>0){
dfs(res,sb.append('('), left-1, right);
sb.deleteCharAt(sb.length()-1);
}
if(right>0){
dfs(res,sb.append(')'), left, right-1);
sb.deleteCharAt(sb.length()-1);
}
}
If we use String here, no need to delete when backtracking
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public ArrayList<String> generateParenthesis(int n) {
ArrayList<String> res = new ArrayList<String>();
String tmp = "";
if(n==0) return res;
dfs(res, tmp, n, n);
return res;
}
privatevoiddfs(ArrayList<String> res, String tmp, int left, int right){
if(left > right) return;
if(left == 0 && right == 0){
res.add(new String(tmp));
return;
}
if(left>0){
dfs(res,tmp+"(", left-1, right);
}
if(right>0){
dfs(res,tmp+")", left, right-1);
}
}
Letter Combinations of a Phone Number
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”].
Iterative Solution
Simple BFS, use a Queue and store all combinations in a list
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public LinkedList<String> letterCombinations(String digits) {
if(digits==null || digits.length()==0) return res; //[""] is not []...
dfs(digits, map, tmp, res, 0);
return res;
}
privatevoiddfs(String digits, String[] map, StringBuilder tmp, ArrayList<String> res, int height){
if(height == digits.length()){
res.add(tmp.toString());
return;
}
int num = digits.charAt(height)-'0';
for(int i=0; i<map[num].length();i++){
tmp.append(map[num].charAt(i));
dfs(digits, map, tmp, res, height+1);
tmp.deleteCharAt(tmp.length()-1); //delete when backtracking..
}
}
Restore IP Addresses
Given a string containing only digits, restore it by returning all possible valid IP address combinations. For example: Given “25525511135”, return [“255.255.11.135”, “255.255.111.35”]. (Order does not matter)
if (tmp.charAt(0)=='0') return tmp.equals("0"); //001 is illegal, only 0 is legal here
int num = Integer.valueOf(tmp);
return num<=255 && num>0;
}
Valid Sudoku
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’. A partially filled sudoku which is valid. Note: A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
