@Yano
2019-09-20T10:49:08.000000Z
字数 4249
阅读 1717
LeetCode
coding 笔记、点滴记录,以后的文章也会同步到公众号(Coding Insight)中,希望大家关注^_^
https://github.com/LjyYano/Thinking_in_Java_MindMapping
https://leetcode.com/problems/word-ladder/description/
Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
Only one letter can be changed at a time.
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
For example,
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> set = new HashSet<>(wordList);
LinkedList<String> queue = new LinkedList<>();
// 在队列中放入初始元素
queue.offer(beginWord);
int step = 2;
while (!queue.isEmpty()) {
// 下一步具有的节点数
int size = queue.size();
while (size > 0) {
String currString = queue.poll();
Iterator<String> iterator = set.iterator();
while (iterator.hasNext()) {
String next = iterator.next();
int diff = diff(next, currString);
// 若当前元素与取出元素差1,并且是endWord,则直接返回结果
if (diff == 1 && next.equals(endWord)) {
return step;
}
// 差1就放入队列,并将其删除(此元素可以删除,因为循环读取时长度不是最优解)
if (diff == 1) {
queue.offer(next);
iterator.remove();
}
}
size--;
}
step++;
}
return 0;
}
private int diff(String s1, String s2) {
if (s1.length() != s2.length()) {
return 0;
}
int diff = 0;
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) != s2.charAt(i)) {
diff++;
}
if (diff >= 2) {
return 2;
}
}
return diff;
}
}
https://leetcode.com/problems/word-ladder-ii/description/
Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
Only one letter can be changed at a time
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
For example,
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
Return
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
Note:
部分可以依照上一题,但是这道题是求「所有的最短路径」,而不是「最短路径长度」,单纯的 BFS 无法实现。但是可以使用 BFS 构造数据结构(保证最短路径),并使用 DFS 求路径。
Version 1:没有构造通用的数据结构,map 的 value 记录步骤,在 DFS 时也要重新计算两个字符串差异数。用 set 表示是否 visit 过。
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
// value:从begin到达该key的最短长度。
Map<String, Integer> map = new HashMap<>();
Set<String> notVisitSet = new HashSet<>(wordList);
List<List<String>> ans = new ArrayList<>();
if (!notVisitSet.contains(endWord)) {
return ans;
}
// 构建map
bfs(beginWord, endWord, map, notVisitSet);
if (map.isEmpty()) {
return ans;
}
map.put(beginWord, 0);
// 从end指向begin,否则会超时!因为begin后面可能接多个路径,但是end只有一个
dfs(endWord, beginWord, map, ans, new ArrayList<>(Arrays.asList(endWord)));
return ans;
}
private void bfs(String beginWord, String endWord, Map<String, Integer> map, Set<String> notVisitSet) {
LinkedList<String> queue = new LinkedList<>();
// 在队列中放入初始元素
queue.offer(beginWord);
boolean find = false;
int level = 1;
while (!queue.isEmpty()) {
int size = queue.size();
while (size > 0) {
String curr = queue.poll();
Iterator<String> iterator = notVisitSet.iterator();
while (iterator.hasNext()) {
String next = iterator.next();
int diff = diff(curr, next);
if (diff == 1) {
// 若在某一步找到,则当前步数结束即可
if (next.equals(endWord)) {
find = true;
}
queue.offer(next);
iterator.remove();
map.put(next, level);
}
}
size--;
}
if (find) {
break;
}
level++;
}
}
private void dfs(String beginWord, String endWord, Map<String, Integer> map, List<List<String>> ans,
List<String> tmp) {
if (beginWord.equals(endWord)) {
List<String> arrayList = new ArrayList<>(tmp);
Collections.reverse(arrayList);
ans.add(arrayList);
return;
}
for (String key : map.keySet()) {
// 要判断 diff,因为本层和下一层没有必然联系
if (map.get(key) == map.get(beginWord) - 1 && diff(beginWord, key) == 1) {
tmp.add(key);
dfs(key, endWord, map, ans, tmp);
tmp.remove(tmp.size() - 1);
}
}
}
private int diff(String s1, String s2) {
if (s1.length() != s2.length()) {
return 0;
}
int diff = 0;
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) != s2.charAt(i)) {
diff++;
}
if (diff >= 2) {
return 2;
}
}
return diff;
}
}