首页 > 代码库 > leetcode Word Ladder
leetcode Word Ladder
给定两个字符串start和end，和一个字符串字典dict，判断从start到end 要经过几次变化，每次变化只能取字典里的词，且相邻的变化只有一个字符不同。例如：
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
思路，这题想了良久也没想出什么好方法。直接来个AC的方法吧。类似输出level order的题目，每层每层的考虑，也就是所谓的BSF。告诉我们只有小写字母其实也是有含义的。就是每次遍历改变一个字母的时候考虑小写的就行了。
以start为数根，它的孩子是和他相距1的字符串，然后判断这些能不能通过改变一个字符变成end。如果可以就返回距离了。如果不可以，就判断改变一个字符之后的字符串是否在dic里面，在的话就加入到que中，que用“”空字符串分开，在之前我们做level order的是用NULL因为que中存的是根节点，这里存的是字符串，所以用空字符。
遇到空字符如果que已经为空了那么就可以返回0了，如果不空，那么就要push空字符代表另一层。
class Solution {public:int ladderLength(string start, string end, unordered_set<string> &dict){ if (dict.size() == 0 || start == end) return 0; if (start.size() != end.size()) return 0; queue<string> que; que.push(start); que.push(""); int dis = 1; while(!que.empty()) { string str = que.front(); que.pop(); if (str != "") { for (int i = 0; i < str.size(); ++i) { for (char j = ‘a‘; j < ‘z‘; ++j) { if (j == str[i]) continue; char tmp = str[i]; str[i] = j; if (str == end) return dis + 1; if (dict.count(str) > 0) { dict.erase(str); que.push(str); } str[i] = tmp; } } } else if (!que.empty()) { que.push(""); dis++; } } return 0;}};
以上做法中需要对push到que中的字符串要在dic中删除，否则会死循环。
网上有提出两个que的，还要swap，觉得比上面的麻烦。不过思路应该是一致的。
leetcode Word Ladder
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。