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 =
endWord =
wordList =
beginWord =
"hit"
endWord =
"cog"
wordList =
["hot","dot","dog","lot","log"]
As one shortest transformation is
return its length
"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.
Solution 1: Use BFS and a set to track each ladder with solve it.
public class Solution {
public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
Set<String> set=new HashSet<>();
set.add(beginWord);
int d=0;
while (!set.isEmpty()) {
wordList.removeAll(set);
Set<String> nextSet=new HashSet<>();
for (String s:set) {
char[] c=s.toCharArray();
for (int i=0; i<c.length; i++) {
char temp=c[i];
for (char r='a'; r<='z'; r++) {
c[i]=r;
String x=new String(c);
if (x.equals(endWord)) return d+2;
else if (wordList.contains(x)) nextSet.add(x);
}
c[i]=temp;
}
}
set=nextSet;
d++;
}
return 0;
}
}
没有评论:
发表评论