题目描述

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

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

样例

输入: 
words = ["oath","pea","eat","rain"] and board =
[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

输出: ["eat","oath"]

说明:
你可以假设所有输入都由小写字母 a-z 组成。

提示:

• 你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯？
• 如果当前单词不存在于所有单词的前缀中，则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作？散列表是否可行？为什么？ 前缀树如何？如果你想学习如何实现一个基本的前缀树，请先查看这个问题： 实现Trie（前缀树）。

算法分析

dfs + 字典树

暴力做法：枚举每个单词，在地图中搜索每个单词的路径，枚举开始位置，然后往4个方向进行搜索，直接搜索会爆时间，因此需要进行优化

用字典树进行剪枝优化

• 1、先将所有的单词放在一个字典树中，在地图中枚举到可以进行搜索的点，从这个点沿着字典树向下的方向进行搜索，而不是4个方向无脑搜索，这样搜所网格时，当前搜索路径构成的前缀字符串在Trie树出现时，才继续往下搜索，否则回溯
• 2、在地图搜索过程中，搜索过的点需要进行赋值为'.'，防止重复使用该字符
• 3、每次dfs搜索时，需要记录从起点沿着搜索路径合并字符记录下来的单词，若某一个位置p.is_end，则把该单词加入到ans，并继续搜索

注意:将单词放进一个字典树的操作可以看 LeetCode 208. 实现 Trie (前缀树)

时间复杂度 $O(n^23^LL)$

详细见 y总分析

Java 代码

class Solution {
    static Node root;
    static int n,m;
    static List<String> ans = new ArrayList<String>();
    static HashSet<String> set = new HashSet<String>();
    static int[] dx = new int[]{-1, 0, 1, 0};
    static int[] dy = new int[]{0, -1, 0, 1};
    static void insert(String word)
    {
        Node p = root;
        for(int i = 0;i < word.length();i ++)
        {
            int u = word.charAt(i) - 'a';
            if(p.son[u] == null) p.son[u] = new Node();
            p = p.son[u];
        }
        p.is_end = true;
    }
    static void dfs(int x,int y, char[][] board, Node p, String pre)
    {
        if(p.is_end) 
        {
            set.add(pre);
        }
        for(int i = 0;i < 4;i ++)
        {
            int a = x + dx[i];
            int b = y + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m) continue;
            if(board[a][b] == '.') continue;
            int u = board[a][b] - 'a';
            if(p.son[u] != null) 
            {
                char t = board[a][b];
                board[a][b] = '.';
                dfs(a, b, board, p.son[u], pre + t);
                board[a][b] = t;
            }
        }
    }
    public List<String> findWords(char[][] board, String[] words) {
        root = new Node();
        ans.clear();
        set.clear();
        n = board.length;
        m = board[0].length;
        int k = words.length;
        for(int i = 0;i < k;i ++) insert(words[i]);

        for(int i = 0;i < n;i ++)
            for(int j = 0;j < m;j ++)
            {
                int u = board[i][j] - 'a';
                if(root.son[u] != null) 
                {
                    char t = board[i][j];
                    board[i][j] = '.';
                    dfs(i, j, board, root.son[u], "" + t);
                    board[i][j] = t;
                }
            }

        for(String s : set) ans.add(s);

        return ans;
    }
}
class Node
{
    boolean is_end;
    Node[] son = new Node[26];
    Node()
    {
        for(int i = 0;i < 26;i ++)
            son[i] = null;
        is_end = false;
    }
}