forked from nyuhuyang/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
word-ladder.py
50 lines (46 loc) · 1.59 KB
/
word-ladder.py
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
# Time: O(n * d), n is length of string, d is size of dictionary
# Space: O(d)
#
# Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
#
# Only one letter can be changed at a time
# Each intermediate word must exist in the dictionary
# For example,
#
# Given:
# start = "hit"
# end = "cog"
# dict = ["hot","dot","dog","lot","log"]
# As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
# return its length 5.
#
# Note:
# Return 0 if there is no such transformation sequence.
# All words have the same length.
# All words contain only lowercase alphabetic characters.
#
# BFS
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):
distance, cur, visited = 0, [start], set([start])
dict.add(end)
while cur:
next = []
for word in cur:
if word == end:
return distance + 1
for i in xrange(len(word)):
for j in 'abcdefghijklmnopqrstuvwxyz':
candidate = word[:i] + j + word[i + 1:]
if candidate not in visited and candidate in dict:
next.append(candidate)
visited.add(candidate)
distance += 1
cur = next
return 0
if __name__ == "__main__":
print Solution().ladderLength("hit", "cog", set(["hot","dot","dog","lot","log"]))