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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
/**
 * Trie
 */
class Solution {

    private Trie root = new Trie();

    private boolean[][] visited;

    private Set<String> ans = new HashSet<>();

    int[] xx = new int[] {-1, 1, 0, 0};
    int[] yy = new int[] {0, 0, -1, 1};

    void buildTrie(String[] words) {
        for (String word : words) {
            root.insert(word);
        }
    }

    List<String> search(char[][] board) {
        ans.clear();
        visited = new boolean[board.length][board[0].length];
        for (int x = 0; x < board.length; x++) {
            for (int y = 0; y < board[0].length; y++) {
                dfs(0, board, "", x, y);
            }
        }
        return new ArrayList<>(ans);
    }

    void dfs(int level, char[][] board, String prefix, int x, int y) {
        // terminator
        if (x < 0 || x > board.length - 1 || y < 0 || y > board[0].length - 1 || visited[x][y]) {
            return;
        }
        prefix += board[x][y];
        if (!root.startsWith(prefix)) {
            return;
        }

        // process current logic
        visited[x][y] = true;
        if (root.search(prefix)) {
            ans.add(prefix);
        }

        // drill down
        for (int i = 0; i < 4; i++) {
            int nx = x + xx[i], ny = y + yy[i];
            dfs(level + 1, board, prefix, nx, ny);
        }

        // revert state
        visited[x][y] = false;
    }
    
    public List<String> findWords(char[][] board, String[] words) {
        if (board == null|| board.length == 0 || words == null || words.length == 0) {
            return Collections.emptyList();
        }
        buildTrie(words);
        return search(board);
    }
}


/**
 * 字典树、前缀树
 */
class Trie {

    private TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        char[] letters = word.toCharArray();
        TrieNode node = root;
        for(char c : letters) {
            int index = c - 'a';
            if (node.getChildren()[index] == null) {
                node.getChildren()[index] = new TrieNode();
            }
            node = node.getChildren()[index];
        }
        node.end();
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        char[] letters = word.toCharArray();
        TrieNode node = root;
        for (char c : letters) {
            int index = c - 'a';
            if (node.getChildren()[index] == null) {
                return false;
            }
            node = node.getChildren()[index];
        }
        return node.isWord();
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        char[] letters = prefix.toCharArray();
        TrieNode node = root;
        for (char c : letters) {
            int index = c - 'a';
            if (node.getChildren()[index] == null) {
                return false;
            }
            node = node.getChildren()[index];
        }
        return true;
    }
}

class TrieNode {

    public static final int MAX = 26;

    private TrieNode[] children;

    private boolean isWord;

    public TrieNode() {
        children = new TrieNode[MAX];
    }

    public void end() {
        this.isWord = true;
    }

    public boolean isWord() {
        return isWord;
    }

    public TrieNode[] getChildren() {
        return children;
    }
}