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 that beginWord is not a transformed word.
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 endWordare 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.
Solution:
Put word list into a set, so that we can check it in O(1).
Using BFS to find the shortest path:
- Create a queue, put begin word in queue
- While queue is not empty, check it layer by layer
- Create all possible word and check with the set, if valid then add into the queue
- Stop condition: when we find end word
class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { Set<String> wordSet = new HashSet<>(wordList); //check contain in O(1) if (!wordSet.contains(endWord)) { return 0; } Queue<String> queue = new LinkedList<>(); queue.offer(beginWord); int cnt = 1; while (!queue.isEmpty()) { //check each possible word in the same level // for (int i = 0; i < queue.size(); i++) { //0, for (int i = queue.size(); i > 0 ; i--) { String word = queue.poll(); //check end or not if (word.equals(endWord)) { return cnt; } //change 1 char, add valid words into queue for (int j = 0; j < word.length(); j++) { char[] newWordArr = word.toCharArray(); for (char ch = 'a'; ch <= 'z'; ch++) { newWordArr[j] = ch; String newWord = new String(newWordArr); if (wordSet.contains(newWord) && newWord != word) { queue.offer(newWord); wordSet.remove(newWord); //avoid duplicate } } } } cnt++; //plus one before go to next level } return 0; } }
Time complexity: O(m * n), m is length of word, n is length of word list.
Space complexity: O(m * n).
Android Playground 