https://leetcode.com/problems/word-ladder/description/
Problem:
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.
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.
Idea:
BFS
Time Complexity: O(n*26^l) -> O(n*26^l/2), l = len(word), n=|wordList|
Space Complexity: O(n)
Solution 1: BFS
C++
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 |
// Author: Huahua // Running time: 93 ms class Solution { public: int ladderLength(string beginWord, string endWord, vector<string>& wordList) { unordered_set<string> dict(wordList.begin(), wordList.end()); if (!dict.count(endWord)) return 0; queue<string> q; q.push(beginWord); int l = beginWord.length(); int step = 0; while (!q.empty()) { ++step; for (int size = q.size(); size > 0; size--) { string w = q.front(); q.pop(); for (int i = 0; i < l; i++) { char ch = w[i]; for (int j = 'a'; j <= 'z'; j++) { w[i] = j; // Found the solution if (w == endWord) return step + 1; // Not in dict, skip it if (!dict.count(w)) continue; // Remove new word from dict dict.erase(w); // Add new word into queue q.push(w); } w[i] = ch; } } } return 0; } }; |
Java
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 |
// Author: Huahua // Running time: 92 ms (<76.61%) class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { Set<String> dict = new HashSet<>(); for (String word : wordList) dict.add(word); if (!dict.contains(endWord)) return 0; Queue<String> q = new ArrayDeque<>(); q.offer(beginWord); int l = beginWord.length(); int steps = 0; while (!q.isEmpty()) { ++steps; for (int s = q.size(); s > 0; --s) { String w = q.poll(); char[] chs = w.toCharArray(); for (int i = 0; i < l; ++i) { char ch = chs[i]; for (char c = 'a'; c <= 'z'; ++c) { if (c == ch) continue; chs[i] = c; String t = new String(chs); if (t.equals(endWord)) return steps + 1; if (!dict.contains(t)) continue; dict.remove(t); q.offer(t); } chs[i] = ch; } } } return 0; } } |
Solution 2: Bidirectional BFS
C++
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 |
// Author: Huahua // Running time: 32 ms (better than 96.6%) class Solution { public: int ladderLength(string beginWord, string endWord, vector<string>& wordList) { unordered_set<string> dict(wordList.begin(), wordList.end()); if (!dict.count(endWord)) return 0; int l = beginWord.length(); unordered_set<string> q1{beginWord}; unordered_set<string> q2{endWord}; int step = 0; while (!q1.empty() && !q2.empty()) { ++step; // Always expend the smaller queue first if (q1.size() > q2.size()) std::swap(q1, q2); unordered_set<string> q; for (string w : q1) { for (int i = 0; i < l; i++) { char ch = w[i]; for (int j = 'a'; j <= 'z'; j++) { w[i] = j; if (q2.count(w)) return step + 1; if (!dict.count(w)) continue; dict.erase(w); q.insert(w); } w[i] = ch; } } std::swap(q, q1); } return 0; } }; |
Java
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 |
// Author: Huahua // Running time: 31 ms (<95.17%) class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { Set<String> dict = new HashSet<>(); for (String word : wordList) dict.add(word); if (!dict.contains(endWord)) return 0; Set<String> q1 = new HashSet<>(); Set<String> q2 = new HashSet<>(); q1.add(beginWord); q2.add(endWord); int l = beginWord.length(); int steps = 0; while (!q1.isEmpty() && !q2.isEmpty()) { ++steps; if (q1.size() > q2.size()) { Set<String> tmp = q1; q1 = q2; q2 = tmp; } Set<String> q = new HashSet<>(); for (String w : q1) { char[] chs = w.toCharArray(); for (int i = 0; i < l; ++i) { char ch = chs[i]; for (char c = 'a'; c <= 'z'; ++c) { chs[i] = c; String t = new String(chs); if (q2.contains(t)) return steps + 1; if (!dict.contains(t)) continue; dict.remove(t); q.add(t); } chs[i] = ch; } } q1 = q; } return 0; } } |
Python
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 |
""" Author: Huahua Running time: 115 ms (better than 96.84%) """ class Solution(object): def ladderLength(self, beginWord, endWord, wordList): wordDict = set(wordList) if endWord not in wordDict: return 0 l = len(beginWord) s1 = {beginWord} s2 = {endWord} wordDict.remove(endWord) step = 0 while len(s1) > 0 and len(s2) > 0: step += 1 if len(s1) > len(s2): s1, s2 = s2, s1 s = set() for w in s1: new_words = [ w[:i] + t + w[i+1:] for t in string.ascii_lowercase for i in xrange(l)] for new_word in new_words: if new_word in s2: return step + 1 if new_word not in wordDict: continue wordDict.remove(new_word) s.add(new_word) s1 = s return 0 |