Welcome to Subscribe On Youtube

127. Word Ladder

Description

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 for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
• 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, and wordList[i] consist of lowercase English letters.
• beginWord != endWord
• All the words in wordList are unique.

Solutions

Solution 1: BFS

BFS minimum step model. This problem can be solved with naive BFS, or it can be optimized with bidirectional BFS to reduce the search space and improve efficiency.

Bidirectional BFS is a common optimization method for BFS, with the main implementation ideas as follows:

1. Create two queues, q1 and q2, for “start -> end” and “end -> start” search directions, respectively.
2. Create two hash maps, m1 and m2, to record the visited nodes and their corresponding expansion times (steps).
3. During each search, prioritize the queue with fewer elements for search expansion. If a node visited from the other direction is found during the expansion, it means the shortest path has been found.
4. If one of the queues is empty, it means that the search in the current direction cannot continue, indicating that the start and end points are not connected, and there is no need to continue the search.

• Java
• C++
• Python
• Go
• C#

• 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;
      }
  }
  

• class Solution {
  public:
      int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
          unordered_set<string> words(wordList.begin(), wordList.end());
          if (!words.count(endWord)) return 0;
          queue<string> q1{ {beginWord} };
          queue<string> q2{ {endWord} };
          unordered_map<string, int> m1;
          unordered_map<string, int> m2;
          m1[beginWord] = 0;
          m2[endWord] = 0;
          while (!q1.empty() && !q2.empty()) {
              int t = q1.size() <= q2.size() ? extend(m1, m2, q1, words) : extend(m2, m1, q2, words);
              if (t != -1) return t + 1;
          }
          return 0;
      }
  
      int extend(unordered_map<string, int>& m1, unordered_map<string, int>& m2, queue<string>& q, unordered_set<string>& words) {
          for (int i = q.size(); i > 0; --i) {
              string s = q.front();
              int step = m1[s];
              q.pop();
              for (int j = 0; j < s.size(); ++j) {
                  char ch = s[j];
                  for (char k = 'a'; k <= 'z'; ++k) {
                      s[j] = k;
                      if (!words.count(s) || m1.count(s)) continue;
                      if (m2.count(s)) return step + 1 + m2[s];
                      m1[s] = step + 1;
                      q.push(s);
                  }
                  s[j] = ch;
              }
          }
          return -1;
      }
  };
  

• # 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
  
  ###########
  
  while q1 and q2:
      if len(q1) <= len(q2):
          # Prioritize the queue with fewer elements for expansion
          extend(m1, m2, q1)
      else:
          extend(m2, m1, q2)
  
  
  def extend(m1, m2, q):
      # New round of expansion
      for _ in range(len(q)):
          p = q.popleft()
          step = m1[p]
          for t in next(p):
              if t in m1:
                  # Already visited before
                  continue
              if t in m2:
                  # The other direction has been searched, indicating that a shortest path has been found
                  return step + 1 + m2[t]
              q.append(t)
              m1[t] = step + 1
  

• 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;
      }
  }
  

All Problems

All Solutions