Lv3. 단어 변환

문제 보기 :  단어 변환

프로그래머스

 

---

문제

• 정답률 : 59%

---

작성 코드

def solution(begin, target, words):
    b = len(begin)
    if target not in words:
        return 0
    
    if begin in words:
        words.remove(begin)
    words.remove(target)
    words.append(target)
    ## 차이가 1만큼 나는 단어들
    allword = [begin] + words
    allword = allword[::-1]
    diff1 = {i:[] for i in allword}
    for i in range(len(allword)):
        k1 = list(allword[i])
        for j in range(i+1,len(allword)):
            dif = 0
            k2 = list(allword[j])
            for kk in range(b):
                if k1[kk] != k2[kk]:
                    dif += 1
                if dif > 1:
                    break
            if dif == 1:
                diff1[allword[i]].append(allword[j])
    answer = 1
    start = diff1[target] #[log,dog] []
    while begin not in start:
        now = []; answer += 1
        for i in start:
            if begin in diff1[i]:
                return answer
            now += diff1[i]
        start = list(set(now))
        
    return answer

---

풀이

begin과 target이 무조건 하나씩만 들어있는 allword 리스트를 만든다. 이때, begin은 맨 앞, target은 맨 뒤에 위치시킨다.

allword를 뒤로 뒤집은 다음, 1씩 차이가 나는 단어들을 딕셔너리로 만들어둔다.
예를 들어, {"cog":["log","dog"],"log":["lot","dog"],"lot":["dot","hot"],"dog":["dot"],"dot":["hot"],"hot":["hit"],"hit":[]}  이런식으로 만들었다.

그 다음, diff1[target]부터 시작해서 가지치기를 시작하면 되는데, 왼쪽 그림처럼 그릴 수 있어서 가지치기라고 칭했다.

그리고 begin 단어가 나오면 answer를 return하는 함수로 코드를 짰다

 

 

• 고려해보면 좋을만한 반례
• "hit", "hot", ["hit", "hot", "lot"] = 1