def possible_word(word, words):
result = []
for i in words:
cnt = 0
if len(word) == len(i):
for a, b in zip(word, i):
if a != b: cnt += 1
if cnt == 1:
result.append(i)
return result
def solution(begin, target, words):
answer = 0
possible = []
def dfs(depth, word, remaining):
remain = remaining.copy()
if depth >= len(words): return
elif word == target:
possible.append(depth)
else:
pos = possible_word(word, remaining)
if not pos: return
else:
for i in pos:
remain.remove(i)
dfs(depth+1, i, remain)
dfs(0, begin, words)
if not possible:
return 0
return min(possible)
