[Programmers] Conversione di parole

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

Soluzione

ref: https://moseory20.tistory.com/31 Inizialmente l’ho risolto con BFS ma non riuscivo a superare il 4o test case, quindi alla fine ho consultato la soluzione di qualcun altro.

I punti chiave erano gli stessi del mio approccio:

Rilevare quando cambia un solo carattere
Se cambia un solo carattere, eseguire il controllo
Memorizzare il risultato del controllo

La differenza era che io l’ho risolto in modo piu’ complesso con la ricorsione, mentre questa persona l’ha risolto in modo pulito con i cicli.

Quando si implementa BFS/DFS con la ricorsione, si definiscono nuovi sottoproblemi tramite i parametri della funzione. La stessa configurazione si puo’ fare con le variabili in un ciclo.

Una cosa che inizialmente mi confondeva era come questa BFS basata su cicli funziona senza confronti di incremento/decremento su answer. Pensavo che ordini di attraversamento diversi potessero produrre valori di answer diversi.

Guardando il codice qui sotto, confronta tutto in una volta piuttosto che sequenzialmente, quindi questo approccio funziona. Dato che tutte le parole vengono accumulate in diff_word in una volta e confrontate, la risposta ottenuta e’ sempre minimizzata.

Codice

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: # differenza di 1 carattere
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