Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:
public class Solution { public int ladderLength(String start, String end, HashSet<String> dict) { if (dict.size() == 0) return 0; LinkedList<String> wordQueue = new LinkedList<String>(); LinkedList<Integer> distanceQueue = new LinkedList<Integer>(); wordQueue.add(start); distanceQueue.add(1); while(!wordQueue.isEmpty()){ String currentWord = wordQueue.pop(); Integer currDistance = distanceQueue.pop(); if(currentWord.equals(end)){ return currDistance; } for(int i = 0 ; i< currentWord.length();i++){ char[] current = currentWord.toCharArray(); for(char c='a';c<='z';c++){//dfs each char to match next potential word current[i] = c; String newWord = new String(current); if(dict.contains(newWord)){ wordQueue.add(newWord); distanceQueue.add(1+currDistance); dict.remove(newWord); } } } } return 0; } }
mistakes: currentWord.equals(end) to compare between strings --> equals to compare value while == compares reference