Question

127. 单词接龙

English Version

题目描述

字典 wordList 中从单词 beginWord_ _和 endWord 的 转换序列 是一个按下述规格形成的序列

 beginWord -> s1 -> s2 -> ... -> sk：

• 每一对相邻的单词只差一个字母。
•  对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord_ _不需要在 wordList 中。
• sk == endWord

给你两个单词_ _beginWord_ _和 endWord 和一个字典 wordList ，返回 _从 beginWord 到 endWord 的 最短转换序列 中的 单词数目_ 。如果不存在这样的转换序列，返回 0 。

 

示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。

 

提示：

• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord、endWord 和 wordList[i] 由小写英文字母组成
• beginWord != endWord
• wordList 中的所有字符串 互不相同

解法

方法一：BFS

BFS 最小步数模型。本题可以用朴素 BFS，也可以用双向 BFS 优化搜索空间，从而提升效率。

双向 BFS 是 BFS 常见的一个优化方法，主要实现思路如下：

1. 创建两个队列 q1, q2 分别用于“起点 -> 终点”、“终点 -> 起点”两个方向的搜索；
2. 创建两个哈希表 m1, m2 分别记录访问过的节点以及对应的扩展次数（步数）；
3. 每次搜索时，优先选择元素数量较少的队列进行搜索扩展，如果在扩展过程中，搜索到另一个方向已经访问过的节点，说明找到了最短路径；
4. 只要其中一个队列为空，说明当前方向的搜索已经进行不下去了，说明起点到终点不连通，无需继续搜索。

while q1 and q2:
  if len(q1) <= len(q2):
    # 优先选择较少元素的队列进行扩展
    extend(m1, m2, q1)
  else:
    extend(m2, m1, q2)


def extend(m1, m2, q):
  # 新一轮扩展
  for _ in range(len(q)):
    p = q.popleft()
    step = m1[p]
    for t in next(p):
      if t in m1:
        # 此前已经访问过
        continue
      if t in m2:
        # 另一个方向已经搜索过，说明找到了一条最短的连通路径
        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;
  }
}

方法二

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
}