海南网络_深圳企业排行榜_周口seo公司_百度推广关键词价格查询

零、原题链接

127. 单词接龙

一、题目描述

字典 wordList 中从单词 beginWord 到 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

• 每一对相邻的单词只差一个字母。
• 对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
• sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

二、测试用例

示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。

提示：

1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord、endWord 和 wordList[i] 由小写英文字母组成
beginWord != endWord
wordList 中的所有字符串 互不相同

三、解题思路

  这题和 433. 最小基因变化 基本思路是一样的，区别就在于单词的长度不固定，单词的字母范围不一样。本质上都是构图+BFS 找最短路径。有下面两种方案：

1. 正向搜索：从起点一直搜索到终点
2. 双向搜索：从起点和终点一直搜索到相交的点

虽然复杂度相同，但是双向搜索的复杂度的系数会小一点。

3.1 BFS

1. 编写计算两个单词的变化次数的函数。
2. 初始化：将起点及其相邻元素入队，并寻找终点
3. 构图：根据 wordList 里面的单词进行构图，只要两个单词字母变化次数小于等于 1 ，就表示这两个单词相邻。
4. BFS：弹出队首元素，判断是否为终点，是则返回步数；不是，则将其邻居（未被访问过）加入搜索队列。

3.2 BFS(双向搜索）

1. 编写计算两个单词的变化次数的函数。
2. 初始化：将起点及其相邻元素入队，并寻找终点。【与 3.1 不同的是，vis 向量表示不一样，>0 表示正向搜索的步长，<0 表示反向搜索的步长，=0 表示未搜索。】
3. 构图：根据 wordList 里面的单词进行构图，只要两个单词字母变化次数小于等于 1 ，就表示这两个单词相邻。
4. BFS：弹出队首元素，判断是否为终点，是则返回步数；不是，则将其邻居（未被访问过）加入搜索队列。【与 3.1 不同的是，这里要考虑正向搜索到反向相交点，反向搜索到正向相交点 和 未搜索的情况。】

四、参考代码

4.1 BFS

时间复杂度：$\mathrm{O}(C{N}^2)$【C 是单词长度，N 是单词个数】
空间复杂度：$\mathrm{O}(C{N}^2)$

class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {int n = wordList.size();vector<vector<bool>> adjMatrix(n, vector<bool>(n, false));vector<bool> vis(n, false);auto change = [&](const string& a, const string& b) {int count = 0;for (int i = 0; i < a.size(); i++) {if (a[i] != b[i])count++;}return count;};// 初始化vector<pair<int, int>> bfs(n + 1);int l = 0, r = 0, end = -1;for (int i = 0; i < n; i++) {if (change(wordList[i], beginWord) <= 1) {bfs[r++] = make_pair(i, 2);vis[i] = true;}if (change(wordList[i], endWord) == 0)end = i;}if (end == -1)return 0;// 构图for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {if (change(wordList[i], wordList[j]) > 1)continue;adjMatrix[i][j] = adjMatrix[j][i] = true;}}// BFSwhile (l < r) {auto item = bfs[l++];if (item.first == end)return item.second;// 添加其邻居for (int i = 0; i < n; i++) {if (vis[i] || !adjMatrix[item.first][i])continue;vis[i] = true;bfs[r++] = make_pair(i, item.second + 1);}}return 0;}
};

4.2 BFS（双向搜索）

时间复杂度：$\mathrm{O}(C{N}^2)$【C 是单词长度，N 是单词个数】
空间复杂度：$\mathrm{O}(C{N}^2)$

class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {int n = wordList.size();vector<vector<bool>> adjMatrix(n, vector<bool>(n, false));vector<int> vis(n, 0);vector<int> bfs(n + 1);auto change = [&](const string& a, const string& b) {int count = 0;for (int i = 0; i < a.size(); i++) {if (a[i] != b[i])count++;}return count;};// 初始化int l = 0, r = 0, end = -1, t;for (int i = 0; i < n; i++) {t = change(wordList[i], beginWord);if (t <= 1) {bfs[r++] = i;vis[i] = t + 1;}if (change(wordList[i], endWord) == 0) {end = i;}}if (end == -1) // 终点不存在return 0;if (vis[end] > 0) // 终点在正向搜索就找到了return vis[end];bfs[r++] = end;vis[end] = -1;// 构图for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {if (change(wordList[i], wordList[j]) > 1)continue;adjMatrix[i][j] = adjMatrix[j][i] = true;}}// BFSwhile (l < r) {auto item = bfs[l++];// 添加其邻居for (int i = 0; i < n; i++) {if (!adjMatrix[item][i])continue;if (vis[i] > 0 && vis[item] < 0) { // 反向搜索到正向相交return vis[i] - vis[item];} else if (vis[i] < 0 && vis[item] > 0) { // 正向搜索到反向相交return vis[item] - vis[i];} else if (vis[i] == 0) { // 未搜索bfs[r++] = i;vis[i] = vis[item] > 0 ? vis[item] + 1 : vis[item] - 1;}}}return 0;}
};