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:
Return 0 if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters. You may assume no duplicates in the word list. You may assume beginWord and endWord are non-empty and are not the same. 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.
/*
Consider this problem as BFS problem we will start with beginword as starting node we will keep exploring its neighhbors
its neighbors are thos which differ by the current node by one character. And once we visited particular word we won't visit that again so we will have neigbhors of current node and now we will search for neighbors for every node in queue and store them in queue and so on until we find lst element.
*/
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
if (beginWord == null || endWord == null || wordList == null || beginWord.length() != endWord.length()) {
return 0;
}
Set<String> words=new HashSet<>(wordList);
if(!words.contains(endWord))
return 0;
if(beginWord.equals(endWord)) return 0;
Deque<String> dq=new ArrayDeque<>(); //to store the nodes at current level
Set<String> visited=new HashSet<>(); //to store visited node
dq.add(beginWord);
visited.add(beginWord);
int distance=1;
while(!dq.isEmpty()){
int wordsInLevel=dq.size(); //we will find the neighbors of every node at each level
for(int i=0;i<wordsInLevel;i++){
String word=dq.removeFirst();
if(word.equals(endWord)){
return distance;
}
for(String neighbor:getNeighbors(word,words)){
if(!visited.contains(neighbor)){
visited.add(neighbor);
dq.add(neighbor);
}
}
}
distance++;
}
return 0;
}
//this function basically tells the neighbors of current node. it changes only one character and check if that charater is in list or not and if it is then that is its neighbor.
public static Set<String> getNeighbors(String word,Set<String>words){
Set<String> validWords=new HashSet<>();
for(int i=0;i<word.length();i++){
char[] chars=word.toCharArray();
for(char ch='a';ch<='z';ch++){
chars[i]=ch;
String temp=new String(chars);
if(words.contains(temp))
validWords.add(temp);
}
}
return validWords;
}
}