Breadth-First Search
Hash Table
String
Backtracking
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
Python3 Java Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66 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 ();
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69 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
}
GitHub