Question

126. Word Ladder II

中文文档

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 _all the shortest transformation sequences from_ beginWord _to_ endWord_, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words _[beginWord, s1, s2, ..., sk].

 

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Explanation: There are 2 shortest transformation sequences:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: []
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

 

Constraints:

• 1 <= beginWord.length <= 5
• endWord.length == beginWord.length
• 1 <= wordList.length <= 500
• wordList[i].length == beginWord.length
• beginWord, endWord, and wordList[i] consist of lowercase English letters.
• beginWord != endWord
• All the words in wordList are unique.
• The sum of all shortest transformation sequences does not exceed 105.

Solutions

Solution 1

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
}