Question

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.

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

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)
        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 not in words:
              continue
            if t == endWord:
              return ans
            q.append(t)
            words.remove(t)
          s[i] = ch
    return 0

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

class Solution {
public:
  int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> words(wordList.begin(), wordList.end());
    queue<string> q{{beginWord}};
    int ans = 1;
    while (!q.empty()) {
      ++ans;
      for (int i = q.size(); i > 0; --i) {
        string s = q.front();
        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)) continue;
            if (s == endWord) return ans;
            q.push(s);
            words.erase(s);
          }
          s[j] = ch;
        }
      }
    }
    return 0;
  }
};

func ladderLength(beginWord string, endWord string, wordList []string) int {
  words := make(map[string]bool)
  for _, word := range wordList {
    words[word] = true
  }
  q := []string{beginWord}
  ans := 1
  for len(q) > 0 {
    ans++
    for i := len(q); i > 0; i-- {
      s := q[0]
      q = q[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 t == endWord {
            return ans
          }
          q = append(q, t)
          words[t] = false
        }
        chars[j] = ch
      }
    }
  }
  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;
  }
}

Solution 2

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()
        step = m1[s]
        s = list(s)
        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

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

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
}