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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class Solution {
    /*分析
    1.要用字典树 可以查前缀是否存在这个前缀
    2.回溯来探四个方向
     */
     boolean[][] bl;
     Set<String> set = new HashSet<>();
     int[][] xy=new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    public List<String> findWords(char[][] board, String[] words) {
        Trie node =new Trie();
        for(String word:words){
                node.add(word);
        }
        int h=board.length;int w=board[0].length;
        bl=new boolean[h][w];
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                bl[i][j]=true;
                huisu(board,node,i,j,""+board[i][j]);
                bl[i][j]=false;
            }
        }
        
        return new ArrayList<>(set);
    }
    //写回溯
    public void huisu(char[][] board,Trie node,int x,int y,String s){
            if(node.searchWord(s)==null)return;
            else if(node.searchWord(s).isempty){
                set.add(s); 
            }
            for(int[] z:xy){
                int a=x+z[0];int b=y+z[1];
                if(a>=0&&b>=0&&a<board.length&&b<board[0].length){
                    if(!bl[a][b]){
                        bl[a][b]=true;
                    huisu(board,node,a,b,s+board[a][b]);
                        bl[a][b]=false;      
                    }
                  
                }
            }
    }


    //先写一个字典树 
    /*
    1.要的方法 ： 添加 查前缀 查单词 
     */
     class Trie{
        private Trie[] children;
        private boolean isempty;
        public Trie(){
            children =new Trie[26];
            isempty=false;
        }
        //添加单词
        public void add(String word){
            Trie node =this;
            for(int i=0;i<word.length();i++){
                char ch=word.charAt(i);
                int index=ch-'a';
                if(node.children[index]==null){
                    node.children[index]=new Trie();
                }
                node=node.children[index];
            }
            node.isempty=true;
        }
        //查单词 返回单词的最后一个字母
        public Trie searchWord(String word){
            Trie node=this;
            for(int i=0;i<word.length();i++){
                char ch=word.charAt(i);
                int index=ch-'a';
                if(node.children[index]==null)return null;
                node=node.children[index];
            }
            return node;
        }
     }
}