搜索二维矩阵
题目链接: https://leetcode.cn/problems/search-a-2d-matrix
解题思路:
遍历每个单词,并将每个单词的某一个字符变为
*
,构建虚拟单词,并构建原单词与虚拟单词的连线若两个单词之间只差一个字符,那么必然能通过虚拟单词将两个单词连通
因此只需要从
beginWord
开始,通过广度优先遍历,找到与endWord
相同的虚拟单词,即可找到最短路径
复杂度分析
时间复杂度: 时间复杂度为, 为矩阵的行数,为举证的列数。
空间复杂度: 空间复杂度为。
最后更新于