抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

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系 的啦。

又或者,这是一个无人踏足之地?


0条评论

发表评论