拼字游戲
這道題其實(shí)就是dfs，思路也是挺清晰的，但是實(shí)現(xiàn)代碼就麻煩些了，最后也是看答案才摸清套路

我的思路基本和答案差不多，首先是利用for loop遍歷每個(gè)字符，然后從這個(gè)字符開始找到該字符為起點(diǎn)的最大匹配的數(shù)目，接下來就是遍歷每個(gè)字符的最大數(shù)目，從這些中取最大的。

兩層dfs嵌套

外層dfs, 遍歷每個(gè)字符，
找到以這個(gè)字符開始的所有匹配的單詞的坐標(biāo)位置List<List<Integer>>，
遍歷這個(gè)list of list,
每個(gè)list其實(shí)就是一個(gè)單詞，用stringbuilder把一個(gè)單詞拼接起來，同時(shí)把這些字符標(biāo)記訪問，然后把單詞裝進(jìn)過渡容器中，和結(jié)果容器比較下大小，如果其大小超越了結(jié)果，那么說明有更多的組合出現(xiàn)，讓其替代結(jié)果容器。 然后進(jìn)行dfs（）其意義就是如果當(dāng)前匹配的是上述單詞，那就把后面開頭的字符的匹配最大情況都找到。

內(nèi)層dfs 較為簡(jiǎn)單，就是一個(gè)利用字典樹去找以某個(gè)字符開頭的所有匹配的情況，將坐標(biāo)化成數(shù)字，利用list<Integer>表示矩陣上的一個(gè)單詞。找到所有可能的匹配。

代碼如下

public class Solution {
    /*
     * @param board: a list of lists of character
     * @param words: a list of string
     * @return: an integer
     */
    
    public int boggleGame(char[][] board, String[] words) {
        // write your code here
        Trie t;
        t = new Trie();
        Trie t1 = t;
        buildT(words, t);
        int m = board.length;
        int n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        List<String> result = new ArrayList<>();
        List<String> path = new ArrayList<>();
        findWords(result, board, visited, path, 0, 0, t);
        return result.size();
    }
    
    private void findWords(List<String> result, char[][] board, boolean[][] visited, List<String> path, int x, int y, Trie t){
        int m = board.length;
        int n = board[0].length;
        for(int i = x; i < m; i++){
            for(int j = y; j < n; j++){
                //得到該位置為起點(diǎn)的所有在詞典中的字符串的下標(biāo)
                if(visited[i][j]){
                    continue;
                }
                List<List<Integer>> ListOfIndexs = new ArrayList<>();
                List<Integer> newP = new ArrayList<>();
                getNextWords(ListOfIndexs, board, visited, newP, i, j, t);
                
                for(List<Integer> indexs: ListOfIndexs){
                    StringBuilder sb = new StringBuilder();
                    for(int index: indexs){
                        visited[index/n][index%n] = true;
                        sb.append(board[index/n][index%n]);
                    }
                    String str = sb.toString();
                    
                    path.add(str);
                    if(path.size() > result.size()){
                        result.clear();
                        result.addAll(path);
                    }
                    findWords(result, board, visited, path, i, j + 1, t);
                    path.remove(path.size() - 1);
                    for(int index: indexs){
                        visited[index/n][index%n] = false;
                    }
                }
                
            }
            // 上面遞歸會(huì)導(dǎo)致穿進(jìn)去的j 成為遞歸內(nèi)的內(nèi)循環(huán)起點(diǎn)，要在下一行歸零
            y = 0;
        }
    }
    

    int []dx = {0, 1, 0, -1};
    int []dy = {1, 0, -1, 0};
    private void getNextWords(List<List<Integer>> words, char[][] board,boolean[][] visited, List<Integer> path, int x, int y, Trie t){
        if(x < 0 | x >= board.length || y < 0 || y >= board[0].length
            || visited[x][y] == true || t.tries[board[x][y] - 'a'] == null) {
            return;
        }
        t = t.tries[board[x][y] - 'a'];
        
        if(t.word != null){
            List<Integer> newP = new ArrayList<>(path);
            newP.add(x * board[0].length + y);
            words.add(newP);
            return;
        }
        path.add(x * board[0].length + y);
        visited[x][y] = true;
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            getNextWords(words, board, visited, path, nx, ny, t);
        }
        visited[x][y] = false;
        path.remove(path.size() - 1);
    }
    
    private void buildT(String[] words, Trie t){
        for(String word: words){
            Trie p = t;
            char[] strs = word.toCharArray();
            for(int i = 0; i < strs.length; i++){
                int index = strs[i] - 'a';
                if(p.tries[index] == null){
                    p.tries[index] = new Trie();
                }
                p = p.tries[index];
            }
            p.word = word;
        }
    }
}

class Trie{
    String word = null;
    Trie[] tries = new Trie[26];
}