단어 변환

• 기초적인 BFS 문제. 현재 단어에서 변환 가능한 단어의 목록을 구해서 각각 탐색하는 것을 BFS 형태로 하면 된다.
• 다만 현재 단어에서 변환 가능한 단어의 목록을 구하는 것은 두가지 방법이 가능하다.
  • 첫번째 방법은, 전체 단어 목록안에 있는 각각의 단어에 대해서 현재 단어로부터 변환이 가능한지를 확인하는 방법이다. 두 단어가 서로 변환가능한지를 체크하는 것은 O(l), 모든 단어에 이 작업을 해야 하니까 시간복잡도는 O(n*l)이 된다 (코드 1)
  • 두번째 방법은, 현재 단어에서 변환이 가능한 단어들을 모두 생성해보면서 각 단어가 전체 단어목록 안에 포함되는지를 확인하는 방법이다. 미리 O(n*l)시간에 모든 단어 목록을 해시테이블에 저장해두자. 이제 특정 단어에서 변환 가능한 단어의 갯수는 O(l*|alphabet|)이고, 이 각각이 단어 목록에 포함되는지는 해시테이블에서 서치하는 O(1)에 가능하다. 결국 시간복잡도는 O(|alphabet|*l) 인데, 여기에서는 영어 소문자만 취급하므로 |alphabet| = 26이다. 상수로 취급해서 날려버리면 그냥 O(l). (코드 2)
• 이 변환 가능한 단어의 목록을 구하는 작업을, 최악의 경우에는 모든 단어에 대해서 수행해야하므로, 전체 시간복잡도는 n을 곱해주면 된다. 첫번째 방식으로 할때는 O(n^2*l). 두번째 방식으로 할때는 전처리 O(n*l)와 서치에 O(n*l)이므로 총 O(n*l)
• 그러나 파이썬으로 두번째 방법을 제대로 구현하는 것은 조금 귀찮다. 파이썬에서는 스트링에서 글자 하나를 치환해서 다른 스트링으로 바꾸는 것이 불가능하다. 리스트로 변환한 상태에서 처리하거나 새로운 스트링을 만들거나 해야 하는데, 리스트로 변환해서 처리하며 set 연산을 위해서 다시 string이나 tuple로 바꿔줘야 하니까 O(l)이 추가로 걸리고, 새로운 스트링을 만드는 것도 그 자체로 O(l)이 걸린다. 그래서 총 시간복잡도가 O(n*l)이 아니라 O(n*l^2)이 된다.
  • 굳이 만들자면 아예 자체 해시펑션을 구현해서, 치환한 스트링의 해시값을 바로 계산해버리면 되기는 하다. 그러면 총 시간복잡도를 O(n*l)로 유지할수는 있다. 구현은 안했다.

"""Solution code for "Programmers 43163. 단어 변환".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/43163
- Solution link: http://www.teferi.net/ps/problems/programmers/43163
"""

from teflib import search


def solution(begin, target, words):

    def convertible_words(cur_word):
        for w in words:
            if sum(1 for c1, c2 in zip(w, cur_word) if c1 != c2) == 1):
                yield w

    dist = search.min_distances(convertible_words, begin, target)
    return dist.get(target, 0)

"""Solution code for "Programmers 43163. 단어 변환".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/43163
- Solution link: http://www.teferi.net/ps/problems/programmers/43163
"""

import string
from teflib import search


def solution(begin, target, words):

    def convertible_words(cur_word):
        for i in range(len(cur_word)):
            left, right = cur_word[:i], cur_word[i+1:]
            for ch in string.ascii_lowercase:
                next_word = left + ch + right
                if next_word in word_set:
                    yield next_word

    word_set = set(words)
    dist = search.min_distances(convertible_words, begin, target)
    return dist.get(target, 0)