LeetCode 79 单词搜索

LeetCode 79 单词搜索题目链接:https://leetcode.

欢迎大家来到IT世界,在知识的湖畔探索吧!

题目链接:

https://leetcode.cn/problems/word-search/

以下是使用Go语言实现外观数列问题的代码:

func exist(board [][]byte, word string) bool {
    // 获取网格的行数和列数
    rows := len(board)
    cols := len(board[0])

    // 创建一个二维数组用于标记已访问的单元格
    visited := make([][]bool, rows)
    for i := range visited {
        visited[i] = make([]bool, cols)
    }

    // 遍历网格中的每个单元格,以检查是否存在单词
    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if board[i][j] == word[0] && backtrack(board, visited, word, i, j, 0) {
                return true
            }
        }
    }

    return false
}

func backtrack(board [][]byte, visited [][]bool, word string, row, col, index int) bool {
    // 检查索引是否达到单词长度,如果是则找到了完整的单词
    if index == len(word) {
        return true
    }

    // 检查单元格是否越界或已访问过,或者当前字母与单词不匹配
    if row < 0 || row >= len(board) || col < 0 || col >= len(board[0]) || visited[row][col] || board[row][col] != word[index] {
        return false
    }

    // 标记当前单元格为已访问
    visited[row][col] = true

    // 在相邻的四个方向上进行回溯
    found := backtrack(board, visited, word, row-1, col, index+1) ||
        backtrack(board, visited, word, row+1, col, index+1) ||
        backtrack(board, visited, word, row, col-1, index+1) ||
        backtrack(board, visited, word, row, col+1, index+1)

    // 还原当前单元格的访问状态,以便在其他路径中继续使用
    visited[row][col] = false

    return found
}

欢迎大家来到IT世界,在知识的湖畔探索吧!

执行用时:120 ms, 在所有 Go 提交中击败了76.58%的用户

内存消耗:1.9 MB, 在所有 Go 提交中击败了84.00%的用户

通过测试用例:85 / 85

解题思路:

这段代码使用了回溯算法来解决问题。主要思路是遍历网格中的每个单元格,找到与单词的第一个字母匹配的单元格作为起点,然后在相邻的四个方向上继续搜索匹配下一个字母的单元格。如果成功匹配整个单词,则返回true,否则返回false。

回溯函数backtrack的参数包括网格board、已访问标记visited、目标单词word、当前单元格的行索引row、列索引col和当前匹配的字母索引index。

在backtrack函数中,首先检查索引是否达到单词长度,如果是则找到了完整的单词,返回true。

然后,检查当前单元格是否越界、已访问过、或者当前字母与目标单词不匹配。如果满足这些条件之一,返回false。

如果当前单元格是一个合法的候选单元格,将其标记为已访问,并在相邻的四个方向上递归调用backtrack函数,尝试匹配下一个字母。如果任何一个方向上的递归调用返回true,则表示找到了匹配的单词,直接返回true。

在递归调用完成后,将当前单元格的访问状态还原,以便在其他路径中继续使用。

最后,如果在当前单元格及其相邻单元格中没有找到匹配的单词,返回false。

在exist函数中,首先获取网格的行数和列数,并创建一个二维数组visited来标记已访问的单元格。

然后,遍历网格中的每个单元格,如果当前单元格的字母与目标单词的第一个字母匹配,并且从当前单元格开始的回溯过程返回true,则表示找到了匹配的单词,直接返回true。

如果遍历完所有的单元格都没有找到匹配的单词,则返回false。

这样,通过回溯算法,可以在给定的二维字符网格中判断目标单词是否存在。

请注意,以上代码假设输入的网格是非空的,并且行数和列数都在有效范围内。在实际应用中,可能需要根据具体要求进行边界条件的判断和错误处理。

时间复杂度:

在exist函数中,需要遍历网格中的每个单元格,因此遍历的时间复杂度为O(m*n),其中m是网格的行数,n是网格的列数。

在backtrack函数中,对于每个单元格,需要在相邻的四个方向上进行递归调用。在最坏的情况下,需要遍历所有的单元格,而每个单元格有四个方向可选,所以递归调用的次数为4^k,其中k是目标单词的长度。因此,递归调用的时间复杂度为O(4^k)。

综上所述,算法的总时间复杂度为O(mn4^k)。

空间复杂度:

在exist函数中,创建了一个二维数组visited来标记已访问的单元格,其大小与网格的大小相同,即O(m*n)。

在backtrack函数中,递归调用的栈空间取决于目标单词的长度k,因为在每一步递归调用中,需要存储当前单元格的行索引、列索引和字母索引。所以递归调用的空间复杂度为O(k)。

综上所述,算法的总空间复杂度为O(m*n + k)。

需要注意的是,以上的时间复杂度和空间复杂度分析是基于回溯算法的情况下,其中每个单元格最多只会被访问一次。如果网格很大且目标单词很长,回溯算法的性能可能会较低。可以考虑通过优化算法或使用其他数据结构来提高性能,如字典树(Trie)等。但在给定的限制条件下,回溯算法是一种可行的解决方案。

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://itzsg.com/35945.html

(0)

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

联系我们YX

mu99908888

在线咨询: 微信交谈

邮件:itzsgw@126.com

工作时间:时刻准备着!

关注微信