-
Notifications
You must be signed in to change notification settings - Fork 1
/
word_ladder.py
69 lines (59 loc) · 2.74 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import unittest
import collections
from typing import List
class Solution:
LOWER_LETTERS = [chr(ord('a') + i) for i in range(26)]
# 更快的解答只能用双向BFS了
def bfs_1(self, begin_word: str, end_word: str, word_list: List[str]) -> int:
if not word_list:
return 0
# 将List转为HashSet提高查询单词的效率
word_set = set(word_list)
# 如果提交到lintcode,因为lintcode上end_word可以不在word_list上,为了统一解答还得把它加进去
# word_set.add(end_word)
if end_word not in word_set:
return 0
queue = collections.deque()
queue.append(begin_word)
visited = set(begin_word)
# 只要是BFS搜索出来的就一定是最短路径(最少步数)
step = 1
# 所有单词都有相同长度
word_len = len(begin_word)
while queue:
# 分层遍历类型题必有的模板语句: for _ in range(len(queue))
# 与之对应的不分层遍历,例如克隆图就没有这一层,不过不分层遍历可以加上这一层
# 可以使用一个<word,distance>的HashMap,就不需要分层遍历的这层for
for _ in range(len(queue)):
word = queue.popleft()
chars = list(word)
for i in range(word_len):
# 保存将要改动单词中的字符
origin_char = chars[i]
# 枚举所有小写字母,将单词第i个字符改为枚举的小写字母
for letter in self.LOWER_LETTERS:
if letter == origin_char:
continue
chars[i] = letter
next_word = ''.join(chars)
if next_word in word_set:
if next_word == end_word:
return step + 1
if next_word not in visited:
queue.append(next_word)
visited.add(next_word)
# 穷举下一位字母前,复原单词
chars[i] = origin_char
# 访问完当前节点的所有邻居,步数+1
step += 1
return 0
class Testing(unittest.TestCase):
TEST_CASES = [
("a", "c", ["b"], 5),
("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"], 5),
("hit", "cog", ["hot", "dot", "dog", "lot", "log"], 0),
]
def test_bfs_1(self):
solution = Solution()
for begin_word, end_word, word_list, shortest_length in self.TEST_CASES:
self.assertEqual(shortest_length, solution.bfs_1(begin_word, end_word, word_list))