Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the dictionary
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:
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
public class Solution { public static int ladderLength(String start, String end, HashSet<String> dict) { int result = 0; if(dict.size() == 0){ return result; } dict.add(start); dict.add(end); result = BFS(start, end, dict); return result; } public static int BFS(String start, String end, HashSet<String> dict){ Queue<String> words = new LinkedList<String>(); Queue<Integer> len = new LinkedList<Integer>(); words.add(start); len.add(1); while(!words.isEmpty()){ String word = words.poll(); int l = len.poll(); if(word.equals(end)){ return l; } for(int i = 0; i< word.length(); i++){ char[] arr = word.toCharArray(); for (char c = ‘a‘; c <= ‘z‘; c++) { if(arr[i] == c){ continue; } arr[i] = c; String str = String.valueOf(arr); if(dict.contains(str)){ words.add(str); len.add(l+1); dict.remove(str); } } } } return 0; } }