Given two words beginWord and endWord, and a dictionary wordList, return the length of the 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.
Return 0 if there is no such transformation sequence.
Example 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5. Example 2:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
Constraints:
1 <= beginWord.length <= 100
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord, endWord, and wordList[i] consist of lowercase English letters.
beginWord != endWord
All the strings in wordList are unique.
Solution:
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Queue<String> queue = new LinkedList<String>();
Set<String> words = new HashSet<>(wordList);
words.remove(beginWord);
queue.add(beginWord);
int level = 0;
while(!queue.isEmpty()){
int size = queue.size();
level++;
for(int i=0;i<size;i++)
{
String currentword = queue.poll();
if(currentword.equals(endWord)) return level;
List<String> neighbors = neighbor(currentword);
for(String neigh:neighbors)
{
if(words.contains(neigh))
{
words.remove(neigh);
queue.add(neigh);
}
}
}
}
return 0;
}
public List<String> neighbor(String s)
{
char[] chars = s.toCharArray();
List<String> result = new ArrayList<>();
for(int i=0;i<chars.length;i++)
{
char temp=chars[i];
for(char c='a';c<='z';c++)
{
chars[i]=c;
String neighbor = new String(chars);
result.add(neighbor);
}
chars[i]=temp;
}
return result;
}
}