Word Search II

https://leetcode.com/problems/word-search-ii/description/

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example,

Given words = ["oath","pea","eat","rain"] and board =

[

['o','a','a','n'],

['e','t','a','e'],

['i','h','k','r'],

['i','f','l','v']

]

Return ["eat","oath"].

Note:

You may assume that all inputs are consist of lowercase letters a-z.

Thoughts

给一组词和一个由字符组成的矩阵，问矩阵里出现过哪些词。问有没有出现过词的问题基本都和Trie有关。Trie也叫prefix tree或字典树, 每个结点代表一个字符，它的children表示字典中的对应词的下一个字符，相同的prefix会有相同的parents。结点还有个特殊分割标志用来记录它是否是某单词的终点。通过遍历Trie就知道哪些词在字典中出现过。搜索和创建单个单词的时间复杂度为O(l), l为单词长度。 空间复杂度为O(lN)。Trie和hash map的比较. trie并不比map快, 取决于hash func, 但一般会有更高的memory. trie的优势在于有很多相同prefix的词, 有固定的查询时间 (hashmap 的collision不可预料)。

这题要找出所有在矩阵中出现过的，因此再配合DFS矩阵使用。

Code

/*
 * @lc app=leetcode id=212 lang=cpp
 *
 * [212] Word Search II
 *
 * https://leetcode.com/problems/word-search-ii/description/
 *
 * algorithms
 * Hard (29.77%)
 * Likes:    1405
 * Dislikes: 78
 * Total Accepted:    132.7K
 * Total Submissions: 440.4K
 * Testcase Example:  '[["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]\n["oath","pea","eat","rain"]'
 *
 * Given a 2D board and a list of words from the dictionary, find all words in
 * the board.
 * 
 * Each word must be constructed from letters of sequentially adjacent cell,
 * where "adjacent" cells are those horizontally or vertically neighboring. The
 * same letter cell may not be used more than once in a word.
 * 
 * 
 * 
 * Example:
 * 
 * 
 * Input: 
 * board = [
 * ⁠ ['o','a','a','n'],
 * ⁠ ['e','t','a','e'],
 * ⁠ ['i','h','k','r'],
 * ⁠ ['i','f','l','v']
 * ]
 * words = ["oath","pea","eat","rain"]
 * 
 * Output: ["eat","oath"]
 * 
 * 
 * 
 * 
 * Note:
 * 
 * 
 * All inputs are consist of lowercase letters a-z.
 * The values of words are distinct.
 * 
 * 
 */
class Solution
{
public:
    class TrieNode
    {
    public:
        vector<TrieNode *> children;
        string word;
        TrieNode(): children(26){}  
    };

    TrieNode *build(vector<string> &words)
    {
        TrieNode *root = new TrieNode(), *node;
        for (const auto &word : words)
        {
            node = root;
            for (const auto c : word)
            {
                const int idx = c - 'a';
                if (node->children[idx] == nullptr)
                    node->children[idx] = new TrieNode();
                node = node->children[idx];
            }
            node->word = word;
        }
        return root;
    }


    void dfs(vector<vector<char>> &board, int i, int j, vector<vector<int>> &dirs, TrieNode *node, vector<string> &res) {
        const int idx = board[i][j] - 'a';
        if (idx >= 26 || node->children[idx] == nullptr) return;
        node = node->children[idx];
        if (node->word != "") {
            res.push_back(node->word);
            node->word = "";
        }
        for (const auto &dir : dirs) {
            int x = i + dir[0], y = j + dir[1];
            if (x >= 0 && x < board.size() && y >= 0 && y < board[0].size()) {
                const char tmp = board[i][j];
                board[i][j] = 'z' + 1;
                dfs(board, x, y, dirs, node, res);
                board[i][j] = tmp;
            }
        }
    }

    vector<string> findWords(vector<vector<char>> &board, vector<string> &words)
    {
        vector<string> res;
        TrieNode *root = build(words);
        vector<vector<int>> dirs = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[0].size(); ++j) {
                dfs(board, i, j, dirs, root, res);
            }
        }
        return res;
    }
};

class Solution {
       public TrieNode buildTrie(String[] words) {
           TrieNode root = new TrieNode(), node;
           for (String word : words) {
               node = root;
               for (int i = 0; i < word.length(); i++) {
                   int index = word.charAt(i) - 'a';
                   if (node.children[index] == null) {
                       node.children[index] = new TrieNode();
                   }
                   node = node.children[index];
               }
               node.word = word;
           }

           return root;
       }

    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word = null;
    }

    static final int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private void dfs(char[][] board, int i, int j, TrieNode node, List<String> res) {
        int index = board[i][j] - 'a';
        if (index >= 26 || node.children[index] == null) {
            return;
        } else {
            node = node.children[index];
            if (node.word != null) {
                res.add(node.word);
                node.word = null;
            }
        }
        for (int[] dir : dirs) {
            int x = i + dir[0], y = j + dir[1];
            if (x >= 0 && x < board.length && y >= 0 && y < board[0].length) {
                board[i][j] ^= 256;
                dfs(board, x, y, node, res);
                board[i][j] ^= 256;
            }
        }
    }

    public List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList<>();
        TrieNode root = buildTrie(words);

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, root, res);
            }
        }

        return res;
    }
}

Analysis

最差时dfs要把整个board都搜索一遍, 外循环有MN次dfs, 因此是O((MN)^2).