Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/127.html
A transformation sequence from word beginWord
to word endWord
using a dictionary wordList
is a sequence of words beginWord -> s1 -> s2 -> ... -> sk
such that:
- Every adjacent pair of words differs by a single letter.
- Every
si
for1 <= i <= k
is inwordList
. Note thatbeginWord
does not need to be inwordList
. sk == endWord
Given two words, beginWord
and endWord
, and a dictionary wordList
, return the number of words in the shortest transformation sequence from beginWord
to endWord
, or 0
if no such sequence exists.
Example 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.
Example 2:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] Output: 0 Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.
Constraints:
1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord
,endWord
, andwordList[i]
consist of lowercase English letters.beginWord != endWord
- All the words in
wordList
are unique.
Algorithm
To improve the search efficiency of our dictionary, we can use a HashSet to store all the words in the dictionary.
Next, we can create a HashMap to establish a mapping between the last word in a path and the length of the path, with the starting word mapped to 1.
To implement the BFS algorithm, we will use a queue data structure. We add the starting word to the queue and start looping over it. At each iteration, we dequeue the first word in the queue and generate all possible replacement words by replacing each character with all 26 letters.
If a replacement word is equal to the target word, we retrieve its length from the hash table and increment it by one.
If a replacement word exists in the dictionary but not in the hash table, we enqueue the replacement word and map its value in the hash table to the previous word’s value plus one.
Once we have dequeued all possible words from the queue and there are no more possible paths to the target word, we return 0 to indicate that there is no path from the start word to the target word in the dictionary.
Code
-
class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { Set<String> words = new HashSet<>(wordList); Queue<String> q = new ArrayDeque<>(); q.offer(beginWord); int ans = 1; while (!q.isEmpty()) { ++ans; for (int i = q.size(); i > 0; --i) { String s = q.poll(); char[] chars = s.toCharArray(); for (int j = 0; j < chars.length; ++j) { char ch = chars[j]; for (char k = 'a'; k <= 'z'; ++k) { chars[j] = k; String t = new String(chars); if (!words.contains(t)) { continue; } if (endWord.equals(t)) { return ans; } q.offer(t); words.remove(t); } chars[j] = ch; } } } return 0; } } public class Word_Ladder { public class Solution { public int ladderLength(String start, String end, Set<String> dict) { // bfs to make sure its shortest if (start.equals(end)) { return 0; } dict.add(end); // !!!@note: 别忘了 Queue<String> q = new LinkedList<String>(); HashSet<String> visited = new HashSet<String>(); int level = 1; int currentLevelCount = 1; int newLevelCount = 0; q.offer(start); visited.add(start); while (!q.isEmpty()) { String s = q.poll(); currentLevelCount--; // @note: 这样少了queue的操作 for (int i = 0; i < s.length(); i++) { char[] array = s.toCharArray(); // @note:@memorize: char array的效率要高 for (char c = 'a'; c <= 'z'; c++) { array[i] = c; String each = new String(array); if (each.equals(end)) { return level + 1; } // @note: 这里没有检查是不是string生成了他自己,因为自己已经在visited里面了。但是还是不太明显,不推荐。 // 加一个if没什么,逻辑更清晰 if (dict.contains(each) && !visited.contains(each)) { q.offer(each); visited.add(each); newLevelCount++; } } } // @note: must be after trying the last word of currentLevel, then update if (currentLevelCount == 0) { currentLevelCount = newLevelCount; newLevelCount = 0; level++; } } return 0; // 如果没找到,那么就是0 } } // 不用string接起来,直接char[] public class Solution_bfs_over_time { public int ladderLength(String start, String end, Set<String> dict) { // bfs to make sure its shortest if (start.equals(end)) return 0; dict.add(end); // !!!@note: 别忘了 Queue<String> q = new LinkedList<String>(); HashSet<String> visited = new HashSet<String>(); int count = 1; q.offer(start); q.offer(null); // null is used marking level end while (!q.isEmpty()) { if (q.peek() == null) { count++; q.poll(); // pop null at head // @note@note: or else, null poll, nulll offer. infinite looping if (q.isEmpty()) break; else { q.offer(null); // enqueue new null continue; } } String s = q.poll(); visited.add(s); char[] array = s.toCharArray(); for (int i = 0; i < s.length(); i++) { char ati = array[i]; for (char c = 'a'; c <= 'z'; c++) { if (c == ati) continue; array[i] = c; String each = new String(array); if (dict.contains(each)) { if (visited.contains(each)) continue; if (each.equals(end)) return count + 1; q.offer(each); } } array[i] = ati; } } return 0; } } public class Solution_recursion_over_time { Set<String> used = new HashSet<>(); int min = Integer.MAX_VALUE; // return: 5 public int ladderLength(String beginWord, String endWord, Set<String> wordList) { // @note@memorize: System.out.println(one.ladderLength("hit", "cog", new HashSet<String>(Arrays.asList("hot","dot","dog","lot","log")))); if (beginWord == null || beginWord.length() == 0 || endWord == null || endWord.length() == 0) { return 0; } // @note: test on char // System.out.println('a' + 1); // output: 98 // System.out.println((char)('a' + 1)); // output: b used.add(beginWord); // @note: dont forget adding it wordList.add(endWord); // @note: dont forget !!! when checking one-step-word validity, endWord should be valid... findLadder(beginWord, endWord, wordList, 0); // begin and end are same, then length==0 return min; } private void findLadder(String beginWord, String endWord, Set<String> wordList, int count) { if (beginWord.equals(endWord)) { min = Math.min(min, count); return; } List<String> all = getWordsOneStepAndInDict(beginWord, wordList); // System.out.println(all.toString()); if (all.size() == 0) { return; } for (int i = 0; i < all.size(); i++) { String next = all.get(i); used.add(next); findLadder(next, endWord, wordList, count + 1); // used.remove(used.size() - 1); // @note:@memorize: HashSet is not remove(index), but remove(object) used.remove(used.size() - 1); } } private boolean isValidWord(String w, Set<String> wordList) { return wordList.contains(w) && !used.contains(w); } private List<String> getWordsOneStepAndInDict(String w, Set<String> wordList) { List<String> result = new ArrayList<>(); // 26 chars, except itself // length * 26, still o(n) though for (int pos = 0; pos < w.length(); pos++) { for (int i = 0; i <= 25; i++) { char newChar = (char)('a' + i); if (w.charAt(pos) != newChar) { String one = w.substring(0, pos) + newChar + w.substring(pos + 1); if (isValidWord(one, wordList)) { // @note: important, avoid infinite looping result.add(one); } } } } return result; } } } ############ class Solution { private Set<String> words; public int ladderLength(String beginWord, String endWord, List<String> wordList) { words = new HashSet<>(wordList); if (!words.contains(endWord)) { return 0; } Queue<String> q1 = new ArrayDeque<>(); Queue<String> q2 = new ArrayDeque<>(); Map<String, Integer> m1 = new HashMap<>(); Map<String, Integer> m2 = new HashMap<>(); q1.offer(beginWord); q2.offer(endWord); m1.put(beginWord, 0); m2.put(endWord, 0); while (!q1.isEmpty() && !q2.isEmpty()) { int t = q1.size() <= q2.size() ? extend(m1, m2, q1) : extend(m2, m1, q2); if (t != -1) { return t + 1; } } return 0; } private int extend(Map<String, Integer> m1, Map<String, Integer> m2, Queue<String> q) { for (int i = q.size(); i > 0; --i) { String s = q.poll(); int step = m1.get(s); char[] chars = s.toCharArray(); for (int j = 0; j < chars.length; ++j) { char ch = chars[j]; for (char k = 'a'; k <= 'z'; ++k) { chars[j] = k; String t = new String(chars); if (!words.contains(t) || m1.containsKey(t)) { continue; } if (m2.containsKey(t)) { return step + 1 + m2.get(t); } q.offer(t); m1.put(t, step + 1); } chars[j] = ch; } } return -1; } }
-
// OJ: https://leetcode.com/problems/word-ladder/ // Time: O(N * W^2) // Space: O(NW) class Solution { public: int ladderLength(string B, string E, vector<string>& A) { unordered_set<string> head, tail, s(begin(A), end(A)); if (s.count(E) == 0) return 0; head.insert(B); tail.insert(E); s.erase(B); s.erase(E); int ans = 2; while (head.size() && tail.size()) { if (head.size() > tail.size()) swap(head, tail); unordered_set<string> next; for (auto w : head) { for (char &c : w) { char tmp = c; for (char ch = 'a'; ch <= 'z'; ++ch) { c = ch; if (tail.count(w)) return ans; if (s.count(w) == 0) continue; next.insert(w); s.erase(w); } c = tmp; } } ++ans; swap(head, next); } return 0; } };
-
# native BFS class Solution: def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int: words = set(wordList) q = deque([beginWord]) ans = 1 while q: ans += 1 for _ in range(len(q)): s = q.popleft() s = list(s) # must convert to list, cannot directly update s[i]='a' for i in range(len(s)): ch = s[i] for j in range(26): # will re-generate s itself # but s not in words-set, s removed after added to words-set s[i] = chr(ord('a') + j) t = ''.join(s) if t not in words: continue if t == endWord: return ans q.append(t) words.remove(t) # equivalent to set t as visited s[i] = ch # restore return 0 ######### ''' 双向 BFS 是 BFS 常见的一个优化方法,主要实现思路如下: 1. 创建两个队列 q1, q2 分别用于“起点 -> 终点”、“终点 -> 起点”两个方向的搜索; 2. 创建两个哈希表 m1, m2 分别记录访问过的节点以及对应的扩展次数(步数); 3. 每次搜索时,优先选择元素数量较少的队列进行搜索扩展,如果在扩展过程中,搜索到另一个方向已经访问过的节点,说明找到了最短路径; 4. 只要其中一个队列为空,说明当前方向的搜索已经进行不下去了,说明起点到终点不连通,无需继续搜索。 ''' class Solution: def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int: def extend(m1, m2, q): for _ in range(len(q)): s = q.popleft() # so, every time, starting from start-word... and later if t in m1 will skip repeated part... step = m1[s] s = list(s) # s = "abc", list(s) ==> ['a', 'b', 'c'] for i in range(len(s)): ch = s[i] for j in range(26): s[i] = chr(ord('a') + j) t = ''.join(s) if t in m1 or t not in words: continue if t in m2: return step + 1 + m2[t] m1[t] = step + 1 q.append(t) s[i] = ch return -1 words = set(wordList) if endWord not in words: return 0 q1, q2 = deque([beginWord]), deque([endWord]) m1, m2 = {beginWord: 0}, {endWord: 0} while q1 and q2: t = extend(m1, m2, q1) if len(q1) <= len(q2) else extend(m2, m1, q2) if t != -1: return t + 1 return 0 ######### import string from collections import deque class Solution(object): def ladderLength(self, beginWord, endWord, wordList): """ :type beginWord: str :type endWord: str :type wordList: Set[str] :rtype: int """ def getNbrs(src, dest, wordList): res = [] for c in string.ascii_lowercase: for i in range(0, len(src)): newWord = src[:i] + c + src[i + 1:] if newWord == src: continue if newWord in wordList or newWord == dest: # about yield https://stackoverflow.com/questions/231767/what-does-the-yield-keyword-do-in-python # yield is a keyword that is used like return, except the function will return a generator. yield newWord queue = deque([beginWord]) length = 0 while queue: length += 1 for k in range(0, len(queue)): top = queue.popleft() for nbr in getNbrs(top, endWord, wordList): wordList.remove(nbr) if nbr == endWord: return length + 1 queue.append(nbr) return 0
-
func ladderLength(beginWord string, endWord string, wordList []string) int { words := make(map[string]bool) for _, word := range wordList { words[word] = true } if !words[endWord] { return 0 } q1, q2 := []string{beginWord}, []string{endWord} m1, m2 := map[string]int{beginWord: 0}, map[string]int{endWord: 0} extend := func() int { for i := len(q1); i > 0; i-- { s := q1[0] step, _ := m1[s] q1 = q1[1:] chars := []byte(s) for j := 0; j < len(chars); j++ { ch := chars[j] for k := 'a'; k <= 'z'; k++ { chars[j] = byte(k) t := string(chars) if !words[t] { continue } if _, ok := m1[t]; ok { continue } if v, ok := m2[t]; ok { return step + 1 + v } q1 = append(q1, t) m1[t] = step + 1 } chars[j] = ch } } return -1 } for len(q1) > 0 && len(q2) > 0 { if len(q1) > len(q2) { m1, m2 = m2, m1 q1, q2 = q2, q1 } t := extend() if t != -1 { return t + 1 } } return 0 }
-
using System.Collections; using System.Collections.Generic; using System.Linq; public class Solution { public int LadderLength(string beginWord, string endWord, IList<string> wordList) { var words = Enumerable.Repeat(beginWord, 1).Concat(wordList).Select((word, i) => new { Word = word, Index = i }).ToList(); var endWordIndex = words.Find(w => w.Word == endWord)?.Index; if (endWordIndex == null) { return 0; } var paths = new List<int>[words.Count]; for (var i = 0; i < paths.Length; ++i) { paths[i] = new List<int>(); } for (var i = 0; i < beginWord.Length; ++i) { var hashMap = new Hashtable(); foreach (var item in words) { var newWord = string.Format("{0}_{1}", item.Word.Substring(0, i), item.Word.Substring(i + 1)); List<int> similars; if (!hashMap.ContainsKey(newWord)) { similars = new List<int>(); hashMap.Add(newWord, similars); } else { similars = (List<int>)hashMap[newWord]; } foreach (var similar in similars) { paths[similar].Add(item.Index); paths[item.Index].Add(similar); } similars.Add(item.Index); } } var left = words.Count - 1; var lastRound = new List<int> { 0 }; var visited = new bool[words.Count]; visited[0] = true; for (var result = 2; left > 0; ++result) { var thisRound = new List<int>(); foreach (var index in lastRound) { foreach (var next in paths[index]) { if (!visited[next]) { visited[next] = true; if (next == endWordIndex) return result; thisRound.Add(next); } } } if (thisRound.Count == 0) break; lastRound = thisRound; } return 0; } }