• 10 Regular Expression Matching
  • 17 Letter Combinations of a Phone Number
  • 22 Generate Parentheses
  • 46 Permutations
  • 89 Gray Code
  • 79 Word Search
  • 140 Word Break II
  • 78 N-Queens
  • 37 Sudoku Solver
  • 52 N-Queens II
  • 93 Restore IP Addresses
  • 131 Palindrome Partitioning
  • 44 Wildcard Matching
  • 60 Permutation Sequence
  • 212 Word Search II
  • 216 Combination Sum III
  • 47 Permutations II
  • 357 Count Numbers with Unique Digits
  • 90 Subsets II
  • 291 Word Pattern II
  • 320 Generalized Abbreviation
  • 401 Binary Watch
  • 40 Combination Sum II
  • 211 Add and Search Word - Data structure design
  • 254 Factor Combinations
  • 267 Palindrome Permutation II
  • 351 Android Unlock Patterns
  • 294 filp games II
  • 526 Beautiful Arrangement

17 Letter Combinations of a Phone Number

思路：先建立数字到字符的映射，然后回溯解决, 可以用map也可以用String 数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void dfs(List<String>res,String digits,String[]num,int ind,String path){
        if(ind==digits.length()){
            res.add(path);
            return;
        }
        if(ind>digits.length())
            return;
        for(int i=0;i<num[digits.charAt(ind)-'2'].length();++i){
            dfs(res,digits,num,ind+1,path+num[digits.charAt(ind)-'2'].charAt(i));
        }
    }
    public List<String> letterCombinations(String digits) {
        String []num = {"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        List<String>res=new ArrayList<>();
        if(digits.isEmpty())
            return res;
        dfs(res,digits,num,0,"");
        return res;
    }

22 Generate Parentheses

思路： 可以用回溯法或者模拟出栈的过程，可以了解下卡塔兰数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public List<String> generateParenthesis(int n) {
        List<String>res=new ArrayList<>();
        generateParenthesis(n,0,0,res,"");
        return res;
    }
    public void generateParenthesis(int n,int left,int right,List<String>res,String path){
        if(left==n && right==n){
            res.add(path);
            return ;
        }
        if(left<n)
            generateParenthesis(n,left+1,right,res,path+"(");
        if(right<left)
            generateParenthesis(n,left,right+1,res,path+")");
    }
    
    
    public void dfs(List<String>res,String path,Stack<Integer>input,Stack<Integer>stk,int n){
        if(path.length()==2*n){
            res.add(path);
            return;
        }
        if(!input.isEmpty()){
            int top = input.pop();
            stk.push(top);
            dfs(res,path+"(",input,stk,n);
            stk.pop();
            input.push(top);
        }
        if(!stk.isEmpty()){
            int top = stk.pop();
            dfs(res,path+")",input,stk,n);
            stk.push(top);
        }
    }
    public List<String>generateParenthesis(int n){
        Stack<Integer> input=new Stack<>();
        Stack<Integer> stk=new Stack<>();
        for(int i=n;i>=1;i--)
            input.push(i);
        List<String>res=new ArrayList<>();
        dfs(res,"",input,stk,n);
        return res;
    }

46 Permutations

思路： 每次都从第一个元素开始，然后判断是不是已经装进path里了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public void dfs(int[]nums,List<List<Integer>>res,List<Integer>path){
        if(path.size()==nums.length){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=0;i<nums.length;++i){
            boolean valid=true;
            for(int x:path){
                if(x==nums[i]){
                    valid=false;
                    break;
                }
            }
            if(valid){
                path.add(nums[i]);
                dfs(nums,res,path);
                path.remove(path.size()-1);
            }
        }
    }
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>>res=new ArrayList<>();
        List<Integer>path=new ArrayList<>();
        dfs(nums,res,path);
        return res;
    }

89 Gray Code

思路： 有计算公式，也可以观察规律，每次都是从以后的数组的后面开始|一个(1<<i)

1
2
3
4
5
6
7
8
9
10
11
public List<Integer> grayCode(int n) {
        List<Integer>res=new ArrayList<>();
        res.add(0);
        for(int i=0;i<n;++i){
            int size=res.size();
            for(int j=size-1;j>=0;--j){
                res.add(res.get(j)|(1<<i));
            }
        }
        return res;
    }

思路： 就是四个方向分别去找，注意不能访问已经访问过的点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public boolean exist(char[][]board,int x,int y,String word,int ind,boolean[][]vis,int[]dx,int[]dy){
        if(word.length()==ind)
            return true;
        if(x>=board.length||x<0||y>=board[0].length||y<0||vis[x][y]||word.charAt(ind)!=board[x][y])
            return false;
        vis[x][y]=true;
        for(int k=0;k<4;++k){
            int nx =x+dx[k];
            int ny =y+dy[k];
            if(exist(board,nx,ny,word,ind+1,vis,dx,dy))
                return true;
        }
        vis[x][y]=false;
        return false;
    }
    public boolean exist(char[][] board, String word) {
        if(board.length==0||board[0].length==0)
            return false;
        int m = board.length,n=board[0].length;
        boolean [][]vis = new boolean[m][n];
        int []dx={1,-1,0,0};
        int []dy ={0,0,1,-1};
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                if(exist(board,i,j,word,0,vis,dx,dy))
                    return true;
            }
        }
        return false;
    }

212 Word Search II

思路： 把这些words装进trie里，然后利用trie进行查找,主要注意的是dfs里的顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class TrieNode {
    public boolean isEnd;
    public TrieNode []children=null;
    public TrieNode(){
        children=new TrieNode[26];
        isEnd=false;
    }
} 
class Trie {
    /** Initialize your data structure here. */
    private TrieNode root;
    public Trie() {
        root=new TrieNode();
    }
    public TrieNode getRoot(){
        return root;
    }
    /** Inserts a word into the trie. */
    public void insert(String word) {
        char []ss=word.toCharArray();
        TrieNode cur=root;
        for(char c:ss){
            TrieNode node=cur.children[c-'a'];
            if(node==null){
                cur.children[c-'a']=new TrieNode();
            }
            cur=cur.children[c-'a'];
        }
        cur.isEnd=true;
    }
}
public class Solution {
  public void dfs(TrieNode node,int x,int y,char[][]board,String path,List<String>res){
        if(node!=null && node.isEnd){
            res.add(path);
            node.isEnd=false;
        }
        if(node==null)
            return;
        if(x<0||x>=board.length||y<0||y>=board[0].length||board[x][y]=='*')
            return;
        char c = board[x][y];
        board[x][y]='*';
        dfs(node.children[c-'a'],x+1,y,board,path+c,res);
        dfs(node.children[c-'a'],x-1,y,board,path+c,res);
        dfs(node.children[c-'a'],x,y+1,board,path+c,res);
        dfs(node.children[c-'a'],x,y-1,board,path+c,res);
        board[x][y]=c;
    }
    public List<String> findWords(char[][] board, String[] words) {
        List<String>res=new ArrayList<>();
        if(board.length==0||board[0].length==0||words.length==0)
            return res;
        int m = board.length,n=board[0].length;
        Trie t = new Trie();
        for(String str:words)
            t.insert(str);
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                dfs(t.getRoot(),i,j,board,"",res);
            }
        }
        return res;
    }
}

140 Word Break II

思路： 递归，然后用dp来memorize。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public List<String>wordBreak(String s,Set<String>sets,Map<String,List<String>>map){
       if(map.containsKey(s))
           return map.get(s);
       List<String>res=new ArrayList<>();
       if(s.isEmpty()){
           res.add("");
           return res;
       }
       int nn=s.length();
       for(int i=1;i<=nn;++i){
           String sub=s.substring(0,i);
           if(sets.contains(sub)){
               //List<String>tmp = wordBreak(s.substring(i),sets,map);
               List<String>tmp = wordBreak(s.substring(i),sets,map);
               for(String str:tmp){
                   res.add(sub+(str.isEmpty()?"":" ")+str);
               }
           }
       }
       map.put(s,res);
       return res;
   }
   public List<String> wordBreak(String s, List<String> wordDict) {
       Set<String>sets=new HashSet<>(wordDict);
       Map<String,List<String>>map=new HashMap<>();
       return wordBreak(s,sets,map);
   }

51 N-Queens && 52

思路： 一个数组记录每行要选的是哪个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public boolean check(int[]dp,int ind){
        //check whether it has conflict with k-1 number
        for(int i=0;i<ind;++i){
            if(dp[i]==dp[ind]||(ind-i)==Math.abs(dp[i]-dp[ind]))
                return false;
        }
        return true;
    }
    
    public void dfs(int[]dp,List<List<String>>res,int ind,int n){
        if(ind==n){
            List<String>tmp=new ArrayList<>();
            for(int ii=0;ii<n;++ii){
                char []ss = new char[n];
                Arrays.fill(ss,'.');
                ss[dp[ii]]='Q';
                tmp.add(String.valueOf(ss));
            }
            res.add(tmp);
            return;
        }
        for(int i=0;i<n;++i){
            dp[ind]=i;
            if(check(dp,ind))
                dfs(dp,res,ind+1,n);
        }
    }
    public List<List<String>> solveNQueens(int n) {
        List<List<String>>res=new ArrayList<>();
        int []dp=new int[n];
        Arrays.fill(dp,-1);
        dfs(dp,res,0,n);
        return res;
    }
    
    
    
    //52 queens II
    public void dfs(int n,int []dp,int[]res,int ind){
        if(ind==n){
            res[0]++;
            return;
        }
        for(int i=0;i<n;++i){
            dp[ind]=i;
            if(check(dp,ind))
                dfs(n,dp,res,ind+1);
        }
    }
    public int totalNQueens(int n) {
        int []dp=new int[n];
        int []res={0};
        Arrays.fill(dp,-1);
        dfs(n,dp,res,0);
        return res[0];
    }

78 Subsets

思路： bitmap， dfs， iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>>res=new ArrayList<>();
        int n = nums.length,m=1<<n;
        for(int i=0;i<m;++i)
            res.add(new ArrayList<>());
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j){
                if(((j>>i)&0x1)!=0)
                    res.get(j).add(nums[i]);
            }
        }
        return res;
    }
    
    
    public void dfs78(List<List<Integer>>res,List<Integer>sub,int[]nums,int ind){
        res.add(new ArrayList<>(sub));
        for(int i=ind;i<nums.length;++i){
            sub.add(nums[i]);
            dfs78(res,sub,nums,i+1);
            sub.remove(sub.size()-1);
        }
    }
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>>res=new ArrayList<>();
        List<Integer>sub=new ArrayList<>();
        dfs78(res,sub,nums,0);
        return res;
    }
    
    
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>>res=new ArrayList<>();
        int n = nums.length;
        if(n==0)
            return res;
        res.add(new ArrayList<>());
        for(int i=0;i<n;++i){
            int size=res.size();
            for(int j=0;j<size;++j){
                List<Integer>tmp = new ArrayList<>(res.get(j));
                tmp.add(nums[i]);
                res.add(tmp);
            }
        }
        return res;
    }

37 sudoku solver

思路： 要用带boolean 的dfs去试探，注意的是判断合法的函数要对啊

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public boolean check(char[][]board,int ind){
        //check row ind/9, col: ind%9, that square;
        boolean []vis=new boolean[9];
        int row = ind/9,col=ind%9;
        for(int i=0;i<9;++i){
            if(board[row][i]=='.')
                continue;
            if(vis[board[row][i]-'1'])
                return false;
            vis[board[row][i]-'1']=true;
        }
        Arrays.fill(vis,false);
        for(int i=0;i<9;++i){
            if(board[i][col]=='.')
                continue;
            if(vis[board[i][col]-'1'])
                return false;
            vis[board[i][col]-'1']=true;
        }
        Arrays.fill(vis,false);
         row=row/3*3;
        col=col/3*3;
        for(int i=row;i<row+3;++i){
            for(int j=col;j<col+3;++j){
                if(board[i][j]=='.')
                    continue;
                if(vis[board[i][j]-'1'])
                    return false;
                vis[board[i][j]-'1']=true;
            }
        }
        return true;
    }
    public boolean dfs37(char[][]board,int ind){
         if(ind==81)
            return true;
        if(board[ind/9][ind%9]!='.'){
            return dfs37(board,ind+1);
        }else{
            for(int i=1;i<=9;++i){
                board[ind/9][ind%9]=(char)(i+'0');
                if(check(board,ind) && dfs37(board,ind+1) ){
                        return true;
                }
                board[ind/9][ind%9]='.';
            }
        }
        return false;
    }
    public void solveSudoku(char[][] board) {
        dfs37(board,0);
    }

93 Restore IP Addresses

思路： 一个一个检测，探测,leading zero的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public boolean valid(String s){
        if(s.isEmpty()||s.length()>3)
            return false;
        if(s.charAt(0)=='0' && s.length()>1)
            return false;
        return Integer.parseInt(s)<=255;
    }
    public void dfs93(List<String>res,String s,int index,List<String> path){
        if(index==s.length() && path.size()==4){
            res.add(String.join(".",path));
            return;
        }
        if(path.size()>4)
            return;
        for(int i=index+1;i<=s.length();++i){
            String sub=s.substring(index,i);
            if(sub.length()>3)
                break;
            if(valid(sub)){
                path.add(sub);
                dfs93(res,s,i,path);
                path.remove(path.size()-1);
            }
        }
    }
    public List<String> restoreIpAddresses(String s) {
        List<String>res=new ArrayList<>();
        if(s.length()<4||s.length()>12)
            return res;
        dfs93(res,s,0,new ArrayList<>());
        return res;
    }

131. Palindrome Partitioning

思路： 可以提前打表也可以后面判断isPalindrome

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public void dfs1311(List<List<String>>res,List<String>path,String s,int ind,boolean[][]palindrome){
        if(ind==s.length()){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=ind+1;i<=s.length();++i){
            if(palindrome[ind+1][i]){
                path.add(s.substring(ind,i));
                dfs1311(res,path,s,i,palindrome);
                path.remove(path.size()-1);
            }
        }
    }
    public List<List<String>>partition(String s){
        List<List<String>>res=new ArrayList<>();
        int m=s.length();
        boolean [][]palindrome=new boolean[m+1][m+1];
        palindrome[0][0]=true;
        for(int i=1;i<=m;++i){
            palindrome[i][i]=true;
            for(int j=i-1;j>=1;--j){
                if(s.charAt(j-1)==s.charAt(i-1) &&( j>=i-2||palindrome[j+1][i-1])){
                    palindrome[j][i]=true;
                }
            }
        }
        dfs1311(res,new ArrayList<>(),s,0,palindrome);
        return res;
    }
    
    
    
    
    public boolean isPalindrome(String ss){
        int begin=0,end=ss.length()-1;
        char []sss=ss.toCharArray();
        while(begin<end){
            if(sss[begin]!= sss[end])
                return false;
            begin++;
            end--;
        }
        return true;
    }
    public void dfs131(List<List<String>>res,List<String>path,String s,int index){
        if(index==s.length()){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=index+1;i<=s.length();++i){
            String sub = s.substring(index,i);
            if(isPalindrome(sub)){
                path.add(sub);
                dfs131(res,path,s,i);
                path.remove(path.size()-1);
            }
        }
    }
    public List<List<String>> partition(String s) {
        List<List<String>>res=new ArrayList<>();
        dfs131(res,new ArrayList<>(),s,0);
        return res;
    }

10 Regular Expression Matching

思路：递归或者是dp


public boolean isMatch(String s, String p) {
        if(p.isEmpty())
            return s.isEmpty();
        if(p.length()==1)
            return s.length()==1 && (s.equals(p)||p.charAt(0)=='.');
        if(s.isEmpty())
            return p.charAt(1)=='*' && isMatch(s,p.substring(2));
        if(p.charAt(1)=='*'){
            //replace 0 or one or more than one
                       return isMatch(s,p.substring(2))||((s.charAt(0)==p.charAt(0)||p.charAt(0)=='.')&&isMatch(s.substring(1),p));

        }else{
            return (s.charAt(0)==p.charAt(0)||p.charAt(0)=='.')&&isMatch(s.substring(1),p.substring(1));
        }
    }

    public boolean isMatch(String s, String p) {
        if(p.isEmpty())
            return s.isEmpty();
        int m= s.length(),n=p.length();
        boolean [][]dp=new boolean[m+1][n+1];
        dp[0][0]=true;
        for(int i=2;i<=n;++i)
            dp[0][i]=dp[0][i-2] && p.charAt(i-1)=='*';
        for(int i=1;i<=m;++i){
            if(i==1)
                dp[i][1]=(s.charAt(i-1)==p.charAt(0))||p.charAt(0)=='.';
            for(int j=2;j<=n;++j){
                if(p.charAt(j-1)=='*'){
                    dp[i][j]=dp[i][j-2]||(s.charAt(i-1)==p.charAt(j-2)||p.charAt(j-2)=='.') && dp[i-1][j];
                }else{
                    dp[i][j]=(s.charAt(i-1)==p.charAt(j-1)||p.charAt(j-1)=='.')&&dp[i-1][j-1];
                }
            }
        }
        return dp[m][n];
    }

Expectations

  • 把dp里的滚动数组搞清楚，节省空间
  • 探索下啤酒鱼怎么做。周末试了试煮鱼，好久没吃过鱼了，表示怀念。

Stanford Univ