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
sifor1 <= i <= kis inwordList. Note thatbeginWorddoes not need to be inwordList. 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 <= 5endWord.length == beginWord.length1 <= wordList.length <= 500wordList[i].length == beginWord.lengthbeginWord,endWord, andwordList[i]consist of lowercase English letters.beginWord != endWord- All the words in
wordListare unique. - The sum of all shortest transformation sequences does not exceed
105.
DFS.
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 ansclass 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
}