use ascii table to solve question
If string consis of all lower english letter, we can define an array of [26]int. 'a' is 97
Leetcode questions
integer to binary string
XOR
//try to find x
5^x = 2
5^5^x = 2^5
0^x = 2^5
x=2^5Linked List
Set (golang does not have set)
Regular Expression
Sort String and remove duplicated characters
Math
Integer boundary
Design
Recursive Memoization
Backtracking
Here is a good explanation for Backtracking. What is Backtracking
One general method to solve combination related backtracking is to use breadth first search tree travesal. I found it is very handy, but may not efficient.
- use a linked list to store element of every level
- initiate the first level
- start a while. Based on the question, decide when to exit the loop
- inside the while loop, level by level using size and poll
Solution for Leetcode 17
class Solution {
public List<String> letterCombinations(String digits) {
List<String> ans = new ArrayList<>();
if (digits.length()==0) return ans;
HashMap<Character, String> map = new HashMap<>();
map.put('2', "abc");
map.put('3', "def");
map.put('4', "ghi");
map.put('5', "jkl");
map.put('6', "mno");
map.put('7', "pqrs");
map.put('8', "tuv");
map.put('9', "wxyz");
int l = digits.length();
LinkedList<String> list = new LinkedList<>();
int h = 0;
//the first level
char c = digits.charAt(h);
String s = map.get(c);
for (int i=0; i<s.length(); i++) {
list.add(Character.toString(s.charAt(i)));
}
while (h<l-1) {
h++;
int size = list.size();
for (int i=0; i<size; i++) {
String s1 = list.poll();
String toAdd = map.get(digits.charAt(h));
for (int j=0; j<toAdd.length(); j++) {
StringBuilder sb = new StringBuilder();
sb.append(s1);
sb.append(toAdd.charAt(j));
list.add(sb.toString());
}
}
}
while (list.size()>0) {
ans.add(list.poll());
}
return ans;
}
}
Check is Parentheses valid
private boolean isValid(String s) {
int left = 0, right = 0;
for (int i=0; i<s.length(); i++) {
char c = s.charAt(i);
if (c=='(') {
left++;
} else {
right++;
}
if (right > left) return false;
}
return left==right;
}