단어 변환
from collections import Counter
def solution(begin, target, words):
if target not in words : return 0
visited = [begin]
que = [x for x in words if sum((Counter(begin)&Counter(x)).values()) == len(begin)-1]
t = 1
while que :
for _ in range(len(que)) :
child = que.pop(0)
if child == target : return t
if child not in visited :
que.extend([x for x in words if sum((Counter(child)&Counter(x)).values()) == len(child)-1])
t += 1
Counter & Counter
Counter끼리 사칙연산 및 논리연산이 가능한점을 이용했다.
Counter('hog')&Counter('dog')
Counter({'o': 1, 'g': 1})
이런식으로 두개의 단어가 겹치는 알파벳의 갯수를 알 수 있다.
(Counter('hog')&Counter('dog')).values()
단어변환은 한글자씩 변해야 하기 때문에 공통 글자 갯수가
글자길이 - 1개인 단어들을 뽑고BFS를 해준다.
- 한 단어의 자식은 글자수 차이가
1만큼 나는 단어들이다.