题目描述

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。

单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

样例描述

思路

Tire树 + 哈希表

1. 将所有的单词放到Trie树上，只要是在树的一个分支上走，就一定会有单词，如果走不通或者没有分支，就说明没有这个单词。
   
2. 哈希表维护所有的单词。
3. 本质上用Tire树来做剪枝，将所有可能的单词（路径）放到Tire树上。

代码

class Solution {
    //构造结点
    class TreeNode{
        String s; //记录当前结尾字符为s
        TreeNode tns[] = new TreeNode[26];
    }      
    TreeNode root = new TreeNode(); //根结点
    //实现Trie插入单词
    public void insert(String word) {
        TreeNode p = root;
        for (char c: word.toCharArray()) {
              int u = c - 'a';
              if (p.tns[u] == null) {
                 p.tns[u] = new TreeNode();
              }  
              p = p.tns[u];
        }
        p.s = word;
    } 
    //标记走过的
    boolean[][] vis = new boolean[15][15];
    //哈希表去重
    Set<String> set = new HashSet<>();
    public List<String> findWords(char[][] board, String[] words) {
          int m = board.length, n = board[0].length;
          //构造Trie树
          for (String s: words) {
              insert(s);
          }
          //枚举起点
          for (int i = 0; i < m; i ++ ) {
              for (int j = 0; j < n; j ++ ) {
                    int u = board[i][j] - 'a';
                    //要有该起点在Trie上有分支才进行枚举
                    if (root.tns[u] != null ) {
                          vis[i][j] = true; //标记走过
                          dfs(board, i, j, root.tns[u]);
                          vis[i][j] = false;
                    }
              }
          }
          List<String> res = new ArrayList<>();
        for (String word: set) {
            res.add(word);
        }
        return res;
    }
    public void dfs(char[][] board, int i, int j, TreeNode p) {
          //当前字符已经是结尾那个，就装入结果集
        if (p.s != null) set.add(p.s);
        int dx[] = new int[]{0, 1, 0, -1};
        int dy[] = new int[]{1, 0, -1 ,0};
        //枚举四个方向 
        for (int d = 0; d < 4; d ++ ) {
            int a = i + dx[d], b = j + dy[d];
            if (a < 0 || b < 0 || a >= board.length || b >= board[0].length || vis[a][b] == true) continue;
            int u = board[a][b] - 'a';
            //只有在Trie上存在分支，才往下走
            if (p.tns[u] != null) {
                 vis[a][b] = true;
            dfs(board, a, b, p.tns[u]);
            vis[a][b] = false;
            }
        }
    }
}