题目描述

给定一个二维字母矩阵，以及一个单词列表。

二维矩阵中一列相邻的字母可以构成一个单词，相邻是指上下左右四个方向相邻，同一位置上的字母只能用一次。
请找出单词列表中有哪些单词出现在二维矩阵中。

样例

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

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

算法

(DFS+Trie) $O(n^23^LL)$

基本思想是暴力搜索出所有单词路径，再判断该路径表示的单词是否出现在单词列表中。枚举所有路径时先枚举起点，再枚举路径延伸的方向。
但朴素DFS搜索空间太大，直接搜会超时。所以我们需要剪枝。

我们先将所有单词存入Trie树中，这样我们在搜索时，如果发现当前单词前缀不在trie中，那么当前的路径一定不会构成任意一个单词，我们直接return。

时间复杂度分析：令 $L$ 表示单词的平均长度，$n$ 表示矩阵边长。则总共有 $n^2$ 个路径起点，每次路径可以往3个方向延伸（一共4个方向，除了第一次以外，其他时候不能往回走，所以每次只剩3个可选的方向），一共延伸 $L$ 次，所以总共有 $n^23^L$ 条不同路径，最坏情况下，每条路径最终都要记录答案，还需要 $O(L)$ 的计算量，所以总时间复杂度是 $O(n^23^LL)$。

C++ 代码

class Solution {
public:

    struct Node
    {
        int id;
        Node *next[26];
        Node()
        {
            id = -1;
            for (int i = 0; i < 26; i ++ )
                next[i] = 0;
        }
    };

    Node *root;

    void insert(string word, int id) {
        Node *p = root;
        for (char c : word)
        {
            int son = c - 'a';
            if (!p->next[son]) p->next[son] = new Node();
            p = p->next[son];
        }
        p->id = id;
    }

    unordered_set<string> hash;
    vector<string> ans;
    vector<vector<bool>> st;
    vector<string> _words;
    int n, m;

    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        if (board.empty()) return ans;
        _words = words;
        root = new Node();
        for (int i = 0; i < words.size(); i ++ ) insert(words[i], i);
        n = board.size(), m = board[0].size();
        st = vector<vector<bool>>(n, vector<bool>(m, false));
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                dfs(board, i, j, root->next[board[i][j]-'a']);
        return ans;
    }

    void dfs(vector<vector<char>>& board, int x, int y, Node *u)
    {
        if (!u) return;
        st[x][y] = true;
        if (u->id != -1)
        {
            string match = _words[u->id];
            if (!hash.count(match))
            {
                hash.insert(match);
                ans.push_back(match);
            }
        }
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        for (int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < m && !st[a][b])
            {
                char c = board[a][b];
                dfs(board, a, b, u->next[c-'a']);
            }
        }
        st[x][y] = false;
    }
};