Please treat this as a interview at a top tech firm, and share your thoughts on how you think I did. Be honest, and leave no stone unturned.
Problem:
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.
Time Complexity: \$O(n^2)\$ (please confirm)
Space complexity: \$O(n)\$
My code:
private static int ladderLength(String start, String end, HashSet<String> dict) {
Deque<String> wordSearch = new ArrayDeque<>();
Deque<Integer> lengthCount = new ArrayDeque<>();
wordSearch.add(start);
lengthCount.add(1);
while(!wordSearch.isEmpty()){
String analyzing = wordSearch.poll();
int curCount = lengthCount.poll();
if(analyzing.equals(end)){
return curCount;
}
for(int j = 0; j < analyzing.length(); j++){
for(char i = 'a'; i <= 'z'; i++){
char[] possibleMatch = analyzing.toCharArray();
possibleMatch[j] = i;
String checkMatch = new String(possibleMatch);
if(dict.contains(checkMatch)){
dict.remove(checkMatch);
lengthCount.add(curCount + 1);
wordSearch.add(checkMatch);
}
}
}
}
return 0;
}