LeetCode.212.单词搜索 II（困难）

题目

LeetCode.212.单词搜索 II（困难）

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

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

题解

解法1：回溯

思路

• 网格中找字典单词，而且还是往相邻单元格找，用深度优先搜索。
• 单词必须按照字母顺序，所以必须尝试从每个单元格开始搜索。
• 只要在网格中找到了一个单词，接下来就不用再找这个单词了。

算法步骤

• 遍历所有单词。
• 遍历网格所有的单元格，在每个单元格用回溯找指定单词，找到一个就停止。

回溯怎么写？

标准的回溯模板写法。

• 用一个访问数组记录已访问过的元素，避免循环搜索。
• 用方向数组简化代码，做好边界检查。
• 回溯结束条件就是单词所有字符遍历完了。

class Solution {
    // 各索引从小到大依次代表 上、右、下、左
    private val deltaRow = intArrayOf(-1, 0, 1, 0)
    private val deltaColumn = intArrayOf(0, 1, 0, -1)

    fun findWords(board: Array<CharArray>, words: Array<String>): List<String> {
        val result = mutableListOf<String>()
        for (word in words) {
            if (findWord(board, word)) {
                result.add(word)
            }
        }
        return result
    }

    private fun findWord(board: Array<CharArray>, word: String): Boolean {
        val rows = board.size
        val columns = board[0].size
        val visited = Array(rows) { BooleanArray(columns) { false } }
        for (row in 0 until rows) {
            for (column in 0 until columns) {
                val found = backtrack(board, row, column, visited, word, 0)
                if (found) return true
            }
        }
        return false
    }

    private fun backtrack(board: Array<CharArray>, row: Int, column: Int, visited: Array<BooleanArray>, word: String, wordIndex: Int): Boolean {
        if (board[row][column] == word[wordIndex]) {
            // 期待的正确情况的边界条件
            if (wordIndex == word.length - 1) return true
            // 单词还没搜完，就继续尝试下一个位置
            visited[row][column] = true
            for (direction in 0..3) {
                val newRow = row + deltaRow[direction]
                val newColumn = column + deltaColumn[direction]
                val rows = board.size
                val columns = board[0].size
                val isInBound = newRow in 0 until rows && newColumn in 0 until columns
                if (isInBound && !visited[newRow][newColumn]) {
                    if (backtrack(board, newRow, newColumn, visited, word, wordIndex + 1)) {
                        return true
                    }
                }
            }
            visited[row][column] = false
        }
        return false
    }
}

解法2：字典树 + 回溯

解法1 的步骤是

• 遍历单词列表选一个单词。
• 从网格中的每个位置开始回溯，看能否找到这个单词。

如果能在网格中的每个位置开始回溯时：

• 发现找到了单词，就能直接记录下来。
• 所走的字符不能构成单词就不要继续做没有意义的搜索了。

这样就是最省时间的。

符合这个访问特点的就是字典树，所以得吧words所有单词先构建出一个字典树。

在网格中的每个位置开始回溯时，用字典树匹配回溯发现的字符，如果能组成单词，就记录下来。

字典树匹配的问题

如果在每个递归层都从字典数的根节点开始匹配，那么会有很多重复判断，可以在回溯递归时，传递字典树的节点给每个递归层，就不会重复判断了。

import java.util.*

class Node(
        var isEnd: Boolean = false,
        val next: Array<Node?> = Array(26) { null }
)

class Trie {
    val root = Node()

    fun insert(word: String) {
        var p = root
        for (c in word) {
            val i = c - 'a'
            if (p.next[i] == null) {
                p.next[i] = Node()
            }
            p = p.next[i]!!
        }
        p.isEnd = true
    }
}

class Solution {
    // 各索引从小到大依次代表 上、右、下、左
    private val deltaRow = intArrayOf(-1, 0, 1, 0)
    private val deltaColumn = intArrayOf(0, 1, 0, -1)

    fun findWords(board: Array<CharArray>, words: Array<String>): List<String> {
        // 所有单词构建字典树
        val trie = Trie()
        for (word in words) {
            trie.insert(word)
        }
        // 回溯
        val result = HashSet<String>()
        val rows = board.size
        val columns = board[0].size
        val visited = Array(rows) { BooleanArray(columns) { false } }
        val path = Stack<Char>()
        for (row in 0 until rows) {
            for (column in 0 until columns) {
                backtrack(board, row, column, visited, trie.root, path, result)
            }
        }
        return result.toList()
    }

    private fun backtrack(
            board: Array<CharArray>,
            row: Int,
            column: Int,
            visited: Array<BooleanArray>,
            node: Node,
            path: Stack<Char>,
            result: HashSet<String>
    ) {
        val c = board[row][column]
        val currentNode = node.next[c - 'a']
        if (currentNode != null) {
            path.push(c)
            visited[row][column] = true
            // 找到一个单词
            if (currentNode.isEnd) {
                // 添加结果
                val sb = StringBuilder()
                for (i in path.indices) {
                    sb.append(path[i])
                }
                result.add(sb.toString())
                // 不能中断搜索，因为字典树当前结点可能还有子树，所以这里找到了一个单词不做return
            }
            // 单词还没搜完，就继续尝试下一个位置
            for (direction in 0..3) {
                val newRow = row + deltaRow[direction]
                val newColumn = column + deltaColumn[direction]
                val rows = board.size
                val columns = board[0].size
                val isInBound = newRow in 0 until rows && newColumn in 0 until columns
                if (isInBound && !visited[newRow][newColumn]) {
                    backtrack(board, newRow, newColumn, visited, currentNode, path, result)
                }
            }
            path.pop()
            visited[row][column] = false
        }
    }
}