[LeetCode] Word Ladder
文章目录
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 intermediate word must exist in the word list
For example,
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["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.
Solution1 single-ended BFS
Typical shortest path problem, use BFS. When using BFS, need to mark visited string. In the problem, we can simply remove it from the dictionary set. Edge case check: remove beginWord from dictionary list if applicable. Tree grows from one side and become unevenly.
Solution2 double-ended BFS
beginSet, endSet stores all the string reachable from beginWord, endWord respectively. The rest process is the same as single-ended BFS. Difference: in each iteration(of one level), use the set that has the fewer string. In this approach, tree grows evenly.
public class Solution {
public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
if (beginWord.equals(endWord)) {
return 1;
}
int len = 2;
Queue<String> begin = new LinkedList<>();
Queue<String> end = new LinkedList<>();
begin.offer(beginWord);
end.offer(endWord);
if (wordList.contains(beginWord)) {
wordList.remove(beginWord);
}
if (wordList.contains(endWord)) {
wordList.remove(endWord);
}
while (!begin.isEmpty() && !end.isEmpty()) {
if (begin.size() > end.size()) {
Queue<String> temp = begin;
begin = end;
end = temp;
}
int size = begin.size();
for (int i = 0; i < size; i++) {
String word = begin.poll();
char[] temp = word.toCharArray();
for (int j = 0; j < temp.length; j++) {
char oldChar = temp[j];
for (char c = 'a'; c <= 'z'; c++) {
temp[j] = c;
String transformed = new String(temp);
if (end.contains(transformed)) {
return len;
} else if (wordList.contains(transformed)) {
wordList.remove(transformed);
begin.offer(transformed);
}
}
temp[j] = oldChar;
}
}
len++;
}
return 0;
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论