38 | 面试题：二维网格中的单词搜索问题

212. 单词搜索 II

解法一：DFS。

思路：枚举候选词首字母，在矩阵中寻找匹配的字符，并以该字段开始做四方向的深度搜索。没找到则换至下一个匹配的字符，以此类推。

存在的问题：对于每一个候选词，都需要做整个矩阵的遍历。

解法二：DFS + 字典树Trie

特点：候选词已经准备好了 => 做预处理

思路：将所有的候选词组成一个字典树，然后枚举矩阵中的元素，在字典树中查找，同时使用深度搜索（四个方向）递归的找出能到达字典树根节点的路径。找不到则说明矩阵中不包含候选词。

代码：先需要一个字典树，代码请看上一篇文章：点我

class Solution {
    val res = HashSet<String>()

    fun findWords(board: Array<CharArray>, words: Array<String>): List<String> {
        val trie = Trie()
        words.forEach {
            trie.insert(it)
        }

        val m = board.size
        val n = board[0].size
        val visited = Array(m) { BooleanArray(n) { false } }

        for (i in 0 until m)
            for (j in 0 until n) {
                dfs(board, visited, "", i, j, trie)
            }

        return res.toList().reversed()
    }

    fun dfs(board: Array<CharArray>, visited: Array<BooleanArray>, str: String, x: Int, y: Int, trie: Trie) {
        if (x < 0 || x >= board.size || y < 0 || y >= board[0].size) return
        if (visited[x][y]) return

        val element = str + board[x][y]

        if (!trie.startsWith(element)) return
        if (trie.search(element)) res.add(element)

        visited[x][y] = true

        dfs(board, visited, element, x - 1, y, trie)
        dfs(board, visited, element, x + 1, y, trie)
        dfs(board, visited, element, x, y - 1, trie)
        dfs(board, visited, element, x, y + 1, trie)

        visited[x][y] = false
    }

    //leetcode 提交时需加上 Trie class
}

大概是这题实在是没人做，于是 自欺欺人尺~：然而都明白，Jvm 再怎么努力也是比不上 C系 的啦。

又或者，这是一个无人踏足之地？