Problem Link:
http://oj.leetcode.com/problems/word-ladder/
Two typical techniques are inspected in this problem:
One simple solution for this problem is BFS from the start word, we keep a list of edge words (the last word of each path). Each time, we search all unvisited words next to the edge words, and add these new found words into the new edge list. The program return the length of the path when the end words is reached, or return 0 if no unvisited words can be found.
However, I implemented this BFS but got a TLE. So I adapted a double-direction BFS which may half the running time, and is accepted by the leetcode judge. The algorithm can go as follows.
Let start_front be the list of edge words of BFS paths from the start word
Let end_front be the list of edge words of BFS paths from the end word
Initialize start_front = [start] and end_front = [end]
Start a double direction BFS loop, in each iteration we extend the two fronts as follows:
For each word w in start_front
Find all transformable words of w those are not visited yet
Let all new found words be the new start_font, return 0 if no new words found
If two fronts meet, then return the number of transforms
For each word w in end_front
Find all transformable words of w those are not visited yet
Let all new found words be the new end_front, return 0 if no new words found
If two fronts meet, then return the number of transforms
The following code is the python implementatation which is accepted by leetcode.com.
|
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85 |
class
Solution: # @param start, a string # @param end, a string # @param dict, a set of string # @return an integer def
ladderLength(self, start, end, dict): """ Suppose start, end, and all words in dict are of the same length. Then we apply BFS from both start and end, and keep track of the two front edges. If the two front meet, then there is a path from start to end. The algorithm can go as follows. 1) Let start_front be the list of words on the edge BFS from start word; 2) Let end_front be the list of words on the edge BFS from end word; 3) Initialize start_front = [start] and end_front = [end] 4) Start a loop where each iteration we do extend two fronts and check if they meet: 1a) Extend the start front to unvisited words 1b) If the start front cannot be extent, it means there is no path between start and end, then return 0. 1c) If the two fronts meet, then return (transform_number + 1) 2a) Extend the end front to unvisited words 2b) If the end front cannot be extent, then return 0 2c) If the two front meet, then return (transform_number + 1) """ # Special cases if
start ==
end: return
1 # The length of words WORD_LENGTH =
len(start) # Initialize the two fronts start_front =
[start] end_front =
[end] # Initialize the number of transforms counter =
0 # Initialize the set of visited words visited =
set() visited.add(start) visited.add(end) # Extend the two fronts and check if they can meet while
True: # Extend the start front new_front =
[] # Suppose the start front can extend counter +=
1 # Check all unvisited words transformed from the start front for
w in
start_front: # Each word in the start front for
i in
xrange(WORD_LENGTH): # Each character in the word for
candidate in
[w[:i]+chr(97+c)+w[i+1:] for
c in
xrange(26)]: # Check if two fronts can meet if
candidate in
end_front: return
counter +
1 # Find all unvisited words from the front and add them as new front if
candidate in
dict and candidate not
in visited: new_front.append(candidate) visited.add(candidate) # Check if there exists any word for the new front if
new_front: start_front =
new_front else: return
0 # Extend the end front new_front =
[] # Suppose the end front can extend counter +=
1 # Check all unvisited words transformed from the end front for
w in
end_front: # Each word in the end front for
i in
xrange(WORD_LENGTH): # Each character in the word for
candidate in
[w[:i]+chr(97+c)+w[i+1:] for
c in
xrange(26)]: # Check if two fronts can meet if
candidate in
start_front: return
counter +
1 # Find all unvisited words from the front and add them as new front if
candidate in
dict and candidate not
in visited: new_front.append(candidate) visited.add(candidate) # Check if there exists any word for the new front if
new_front: end_front =
new_front else: return
0 |
【LeetCode OJ】Word Ladder I,布布扣,bubuko.com
原文：http://www.cnblogs.com/zzzdevil/p/3704788.html