[Programmers] Word Conversion

https://programmers.co.kr/learn/courses/30/lessons/43163

Solution

ref: https://moseory20.tistory.com/31 I initially solved it with BFS but couldn’t pass the 4th test case, so I ended up looking at someone else’s solution.

The key points were the same as my approach:

Detect when only one character differs
If only one character differs, run the check
Store the check result

The difference was that I solved it more complexly with recursion, while this person solved it cleanly with loops.

When implementing BFS/DFS with recursion, you define new subproblems through the function parameters. The same setup can be done with variables in a loop.

One thing that confused me at first was how this loop-based BFS works without increment/decrement comparisons on answer. I thought there should be cases where different traversal orders produce different answer values.

Looking at the code below, it compares everything at once rather than sequentially, so this approach works. Since all words are stacked into diff_word at once and compared, the answer obtained is always minimized.

Code

ref: https://moseory20.tistory.com/31

1
def solution(begin, target, words):
2
    if target not in words:
3
        return 0
4

5
    answer = 0
6
    word_len = len(begin)
7
    word_list = [begin]
8
    diff_word = list()
9

10
    while(1):
11
        for wl in word_list:
12
            diff_word.clear()
13
            for word in words:
14
                diff = 0
15
                for idx in range (0, word_len):
16
                    if wl[idx] != word[idx]: diff += 1
17
                    if diff > 1: break
18
                if diff==1: # 1 character difference
19
                    diff_word.append(word)
20
                    words.remove(word)
21

22
        answer += 1
23
        if target in diff_word: return answer
24
        else: word_list = diff_word
25

26
    return answer