Question

126. 单词接龙 II

English Version

题目描述

按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列，并满足：

• 每对相邻的单词之间仅有单个字母不同。
• 转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。
• sk == endWord

给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表_ _[beginWord, s1, s2, ..., sk] 的形式返回。

 

示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
解释：存在 2 种最短的转换序列：
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：[]
解释：endWord "cog" 不在字典 wordList 中，所以不存在符合要求的转换序列。

 

提示：

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

解法

方法一

class Solution:
  def findLadders(
    self, beginWord: str, endWord: str, wordList: List[str]
  ) -> List[List[str]]:
    def dfs(path, cur):
      if cur == beginWord:
        ans.append(path[::-1])
        return
      for precursor in prev[cur]:
        path.append(precursor)
        dfs(path, precursor)
        path.pop()

    ans = []
    words = set(wordList)
    if endWord not in words:
      return ans
    words.discard(beginWord)
    dist = {beginWord: 0}
    prev = defaultdict(set)
    q = deque([beginWord])
    found = False
    step = 0
    while q and not found:
      step += 1
      for i in range(len(q), 0, -1):
        p = q.popleft()
        s = list(p)
        for i in range(len(s)):
          ch = s[i]
          for j in range(26):
            s[i] = chr(ord('a') + j)
            t = ''.join(s)
            if dist.get(t, 0) == step:
              prev[t].add(p)
            if t not in words:
              continue
            prev[t].add(p)
            words.discard(t)
            q.append(t)
            dist[t] = step
            if endWord == t:
              found = True
          s[i] = ch
    if found:
      path = [endWord]
      dfs(path, endWord)
    return ans

class Solution {
  private List<List<String>> ans;
  private Map<String, Set<String>> prev;

  public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
    ans = new ArrayList<>();
    Set<String> words = new HashSet<>(wordList);
    if (!words.contains(endWord)) {
      return ans;
    }
    words.remove(beginWord);
    Map<String, Integer> dist = new HashMap<>();
    dist.put(beginWord, 0);
    prev = new HashMap<>();
    Queue<String> q = new ArrayDeque<>();
    q.offer(beginWord);
    boolean found = false;
    int step = 0;
    while (!q.isEmpty() && !found) {
      ++step;
      for (int i = q.size(); i > 0; --i) {
        String p = q.poll();
        char[] chars = p.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 (dist.getOrDefault(t, 0) == step) {
              prev.get(t).add(p);
            }
            if (!words.contains(t)) {
              continue;
            }
            prev.computeIfAbsent(t, key -> new HashSet<>()).add(p);
            words.remove(t);
            q.offer(t);
            dist.put(t, step);
            if (endWord.equals(t)) {
              found = true;
            }
          }
          chars[j] = ch;
        }
      }
    }
    if (found) {
      Deque<String> path = new ArrayDeque<>();
      path.add(endWord);
      dfs(path, beginWord, endWord);
    }
    return ans;
  }

  private void dfs(Deque<String> path, String beginWord, String cur) {
    if (cur.equals(beginWord)) {
      ans.add(new ArrayList<>(path));
      return;
    }
    for (String precursor : prev.get(cur)) {
      path.addFirst(precursor);
      dfs(path, beginWord, precursor);
      path.removeFirst();
    }
  }
}

func findLadders(beginWord string, endWord string, wordList []string) [][]string {
  var ans [][]string
  words := make(map[string]bool)
  for _, word := range wordList {
    words[word] = true
  }
  if !words[endWord] {
    return ans
  }
  words[beginWord] = false
  dist := map[string]int{beginWord: 0}
  prev := map[string]map[string]bool{}
  q := []string{beginWord}
  found := false
  step := 0
  for len(q) > 0 && !found {
    step++
    for i := len(q); i > 0; i-- {
      p := q[0]
      q = q[1:]
      chars := []byte(p)
      for j := 0; j < len(chars); j++ {
        ch := chars[j]
        for k := 'a'; k <= 'z'; k++ {
          chars[j] = byte(k)
          t := string(chars)
          if v, ok := dist[t]; ok {
            if v == step {
              prev[t][p] = true
            }
          }
          if !words[t] {
            continue
          }
          if len(prev[t]) == 0 {
            prev[t] = make(map[string]bool)
          }
          prev[t][p] = true
          words[t] = false
          q = append(q, t)
          dist[t] = step
          if endWord == t {
            found = true
          }
        }
        chars[j] = ch
      }
    }
  }
  var dfs func(path []string, begin, cur string)
  dfs = func(path []string, begin, cur string) {
    if cur == beginWord {
      cp := make([]string, len(path))
      copy(cp, path)
      ans = append(ans, cp)
      return
    }
    for k := range prev[cur] {
      path = append([]string{k}, path...)
      dfs(path, beginWord, k)
      path = path[1:]
    }
  }
  if found {
    path := []string{endWord}
    dfs(path, beginWord, endWord)
  }
  return ans
}