[LeetCode] 127. Word Ladder

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWordto endWord, such that:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

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.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

UPDATE (2017/1/20):
The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Thought process:

1. Build graph: a hash map whose key is the word and value is its neighbors. Map<String, List<String>>.
2. BFS: use a hash set to keep track of visited words. 

Note that wordList does not contain beginWord. Don't forget to add it to wordList before building graph. 

Solution 1:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

public class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { wordList.add(beginWord); Map<String, List<String>> graph = new HashMap<>(); for (int i = 0; i < wordList.size(); i++) { for (int j = i + 1; j < wordList.size(); j++) { String word1 = wordList.get(i); String word2 = wordList.get(j); List<String> neighbors1 = graph.getOrDefault(word1, new ArrayList<>()); List<String> neighbors2 = graph.getOrDefault(word2, new ArrayList<>()); if (areNeighbors(word1, word2)) { neighbors1.add(word2); neighbors2.add(word1); } graph.put(word1, neighbors1); graph.put(word2, neighbors2); } } Queue<String> queue = new LinkedList<>(); Set<String> visited = new HashSet<>(); queue.offer(beginWord); visited.add(beginWord); int length = 0; while (!queue.isEmpty()) { length++; int size = queue.size(); for (int i = 0; i < size; i++) { String current = queue.poll(); if (current.equals(endWord)) { return length; } visited.add(current); for (String neighbor : graph.get(current)) { if (!visited.contains(neighbor)) { queue.offer(neighbor); } } } } return 0; } private boolean areNeighbors(String s1, String s2) { boolean hasDifferentChar = false; for (int i = 0; i < s1.length(); i++) { if (s1.charAt(i) != s2.charAt(i)) { if (hasDifferentChar) { return false; } hasDifferentChar = true; } } return true; } }

Time complexity:

Say there are V words, E edges, and every word's length is l. areNeighbors() takes O(l). So building the graph takes O(V^2 l). BFS takes O(V + E). The overall time complexity is O(V^2 l).

Unfortunately, this standard solution exceeded the time limit of LeetCode's super picky judge. So I have to use a hacky way to solve this. I can skip building the graph, and start doing BFS on beginWord directly. For each word, I iterate through its characters. For each character, I change it to all other characters in a - z, and check if word list has it. To ensure constant time searching in word list, I need to copy it into a hash set first.

Solution 2:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

public class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { Set<String> wordSet = new HashSet<>(wordList); Queue<String> queue = new LinkedList<>(); queue.offer(beginWord); Set<String> visited = new HashSet<>(); visited.add(beginWord); int length = 0; while (!queue.isEmpty()) { length++; int size = queue.size(); for (int i = 0; i < size; i++) { String current = queue.poll(); if (current.equals(endWord)) { return length; } char[] chars = current.toCharArray(); for (int j = 0; j < chars.length; j++) { char temp = chars[j]; for (char ch = 'a'; ch <= 'z'; ch++) { chars[j] = ch; String s = new String(chars); if (wordSet.contains(s) && !visited.contains(s)) { queue.offer(s); visited.add(s); } } chars[j] = temp; } } } return 0; } }

Time complexity:
The while loop and the first for loop iterates through all words, which is O(V). The third for loop iterates through a word's characters, which is O(l). The third for loop is O(1). So the overall time complexity is O(Vl).