lintcode635 拼字游戏

拼字游戏
这道题其实就是dfs，思路也是挺清晰的，但是实现代码就麻烦些了，最后也是看答案才摸清套路

我的思路基本和答案差不多，首先是利用for loop遍历每个字符，然后从这个字符开始找到该字符为起点的最大匹配的数目，接下来就是遍历每个字符的最大数目，从这些中取最大的。

两层dfs嵌套

外层dfs, 遍历每个字符，
找到以这个字符开始的所有匹配的单词的坐标位置List<List<Integer>>，
遍历这个list of list,
每个list其实就是一个单词，用stringbuilder把一个单词拼接起来，同时把这些字符标记访问，然后把单词装进过渡容器中，和结果容器比较下大小，如果其大小超越了结果，那么说明有更多的组合出现，让其替代结果容器。 然后进行dfs（）其意义就是如果当前匹配的是上述单词，那就把后面开头的字符的匹配最大情况都找到。

内层dfs 较为简单，就是一个利用字典树去找以某个字符开头的所有匹配的情况，将坐标化成数字，利用list<Integer>表示矩阵上的一个单词。找到所有可能的匹配。

代码如下

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++){
                //得到该位置为起点的所有在词典中的字符串的下标
                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;
                    }
                }
                
            }
            // 上面递归会导致穿进去的j 成为递归内的内循环起点，要在下一行归零
            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];
}