lintcode-120-单词接龙
2024-08-27 00:52:37
120-单词接龙
给出两个单词（start和end）和一个字典，找到从start到end的最短转换序列
比如：
每次只能改变一个字母。
变换过程中的中间单词必须在字典中出现。注意事项
- 如果没有转换序列则返回0。
- 所有单词具有相同的长度。
- 所有单词都只包含小写字母。
样例
给出数据如下：
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
一个最短的变换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog"，
返回它的长度 5标签
领英 宽度优先搜索
思路
可以将此题理解为求图中两点的最短路径，dict 中每个单词是一个节点，start 与 end 也是图中的节点，若两个单词中只有一个字母不同（如 "hit" "hot" "dog"）在，则这两个节点是联通的。故问题就转化成了在图中求节点 start 到节点 end 的最短路径。
因为只需要知道路径长度而非具体路径，所以可以简单使用宽度优先搜索，从 start 开始搜索 end，每扩大一层，路径长度 +1
方法一（最开始想到的，但提交超时）
使用队列 path 记录搜索顺序，pathCount 记录每个节点与 start 节点的距离（即路径长度），每次将与对列的头节点相连且未遍历的节点加入到队列并标记其已经遍历，更新此节点距离
code
class Solution {
public:
/**
* @param start, a string
* @param end, a string
* @param dict, a set of string
* @return an integer
*/
int ladderLength(string start, string end, unordered_set<string> &dict) {
// write your code here
int size = dict.size();
if (size <= 0) {
return 0;
}
dict.insert(end);
map<string, bool> isVisited;
map<string, int> pathCount;
queue<string> path;
path.push(start);
isVisited[start] = true;
pathCount[start] = 1;
pathCount[end] = 0;
while (!path.empty()) {
string last = path.front();
path.pop();
for (string str : dict) {
if (isVisited[str] == false && isConnect(str, last)) {
path.push(str);
isVisited[str] = true;
pathCount[str] = pathCount[last] + 1;
if (str == end) {
return pathCount[end];
}
}
}
}
return pathCount[end];
}
bool isConnect(string str1, string str2) {
int distance = 0;
for (int i = 0; i < str1.size(); i++) {
if (str1[i] != str2[i]) {
distance++;
if (distance > 1) {
return false;
}
}
}
if (distance == 1) {
return true;
}
else {
return false;
}
}
};
方法二（AC）
网上普遍的解法，在遍历节点的相邻节点处做了优化，在得到队列头结点时，枚举所有与头结点相连的节点值，并判断此值是否在图中（即 dict 中）。若此节点未被遍历过（即此节点存在于 dict），将其加入队列并更新距离，然后将此节点删除（减少搜索代价），否则，继续枚举
code
class Solution {
public:
/**
* @param start, a string
* @param end, a string
* @param dict, a set of string
* @return an integer
*/
int ladderLength(string start, string end, unordered_set<string> &dict) {
// write your code here
int size = dict.size();
if (size <= 0) {
return 0;
}
if(start.size() == end.size() && start.size() == 1) {
return 1;
}
map<string, int> pathCount;
queue<string> path;
path.push(start);
pathCount[start] = 1;
dict.erase(start);
dict.insert(end);
while (dict.size() > 0 && !path.empty()) {
string last = path.front();
path.pop();
for (int i = 0; i < last.size(); i++) { // 枚举可能相连的节点值
string str = last;
for (char j = 'a'; j <= 'z'; j++) { // 枚举可能相连的节点值
if (str[i] == j) {
continue;
}
else {
str[i] = j;
}
if (dict.find(str) != dict.end()) { // 枚举的值在图中存在且未被遍历
path.push(str);
pathCount[str] = pathCount[last] + 1;
dict.erase(str);
}
if (str == end) { // 找到
return pathCount[end];
}
}
}
}
return 0;
}
};
最新文章
- android-studio设置代理
- AsyncTask和Handler对比（转）
- nginx连接php fastcgi配置
- java5 CountDownLatch同步工具
- 使用phonegap + appframework2.0框架
- poj 2503 快排+二分
- U制作LFS linux
- 从ulimit命令看socket的限制
- win8系统特别慢的基本判断方法
- android.telephony.SmsManager 短信笔记
- Activity进程和线程之间的关系
- 51nod 1092（lcs）回文字符串
- 【js】AddFavorite/SetHome提醒用户自行操作加入收藏/设置主页
- Docker 入门（Mac环境）-part 1 入门基本操作
- tfs代码上传到server并下载到新位置
- python-淘宝信息定向爬取
- jieba库的使用与词云
- for-in循环
- 网罗收集10046的各种Case，方便trace信息的收集
- My97DatePicker：开始时间和结束时间的最大间隔为1个月30天，并且不大于当前时间（3种方法）