1from collections import namedtuple, deque
2import string
3class Solution:
4 def stringTransformation(self, dict, s, t):
5 return self.bfs(dict, s, t)
6
7 def bfs(self, dict, s, t):
8 word = namedtuple("word", ("str", "dist"))
9 start = word(s, 0)
10 queue = deque([start])
11 dict.remove(s)
12 while queue:
13 w, d = queue.popleft()
14 if w == t: return d
15
16 for i in range(len(w)):
17 for c in string.ascii_lowercase:
18 cand = w[:i] + c + w[i + 1:]
19 if cand in dict:
20 dict.remove(cand)
21 queue.append((cand, d + 1))
22
23 return -1