Hamming Distance usando un dizionario

Puoi risolverlo con una ricerca di ampiezza standard, con l'aggiunta del salvataggio del percorso effettuato su un nodo ogni volta che lo accodati nella coda to search . Gli algoritmi BFS evitano i loop mantenendo un visited o discovered impostato. Poiché utilizzano una coda anziché uno stack, normalmente non vengono implementati utilizzando la ricorsione, a meno che l'implementazione non utilizzi strutture di dati immutabili.

Se raggiungi un punto nell'algoritmo in cui non ci sono più residui nella coda to search , sai che non esiste un percorso possibile. Nota a questo punto, il set visited contiene tutti i nodi raggiungibili dal punto iniziale dato. Puoi approfittare di questo per calcolare e memorizzare tutti i set di parole collegate, saltando semplicemente la parte in cui controlli se hai raggiunto la parola obiettivo. Tuttavia, è più semplice e potrebbe spesso funzionare più velocemente per eseguire semplicemente BFS.

Sembra che quello che stai cercando di fare è capire se due nodi in un grafico si trovano nello stesso componente connesso . Nello specifico, il grafico è un non indiretto in cui le parole del tuo dizionario sono nodi e due nodi sono connessi l'un l'altro da un vertice quando differiscono esattamente di una lettera e hanno la stessa lunghezza. La radice del problema è che questo grafico non è totalmente connesso . Potrebbe essere un grafico disconnesso di componenti connessi reciprocamente irraggiungibili. Infatti, dalla tua descrizione sembra che qualsiasi parola con un diverso numero di lettere debba essere in componenti separati.

Le parole chiave in corsivo sopra sono troppo tecniche per spiegare completamente una risposta qui, ma le troverai su Wikipeida, o in qualsiasi testo di informatica che copra algoritmi di grafi. Gli algoritmi da prendere in considerazione per risolvere il problema sono gli algoritmi raggiungibilità per i grafi disconnessi e non orientati.

Per risolvere la domanda che poni, devi capire completa ricerca , e per questo devi capire algoritmi ricorsivi . Ciò significa semplicemente che devi ridurre ad es. il problema di raggiungere "tree" da "full" al problema di raggiungere "free" da "full" e gestire correttamente i dati intermedi.

Suppongo che stai usando la ricorsione per questo. Ogni trasformazione è un'unità di lavoro da svolgere, si spera che venga gestita in un metodo o in un gruppo di metodi.

Quando salti alla parola successiva, tieni traccia di tutte le parole che hai già visto durante questo specifico percorso e controlla le opzioni disponibili rispetto all'elenco di quelle parole per escludere quelle che hai già visitato.

Esempio:

heist- (1) - > feist- (2) - > feast- (3) - > feaseX - (4) - > fiamma

* I numeri significano il ciclo di esecuzione dello stesso metodo. Versione semplificata a scopo dimostrativo.

public string[] previouslyUsedWords = new String[]();

public string transformNext(string currentWord) {
    var possibleOptions = _optionsProvider.GetOptions(currentWord);

    foreach(var word in possibleOptions) {
        if(!previouslyUsedWords.Contains(word)) {
            previouslyUsedWords.Add(word);
            return word;
        }
    }

    throw new Exception("No options left, this is a dead end!");
}

Combina questo con un algoritmo tree-traversal (alcuni percorsi sono senza connessione ed è per questo che devi tornare indietro e provare altri percorsi) e dovresti eseguire questa operazione in pochissimo tempo.

Penso che dovresti probabilmente usare un algoritmo di ritrovamento dell'unione per trovare tutti i gruppi collegati di parole di n-lettere che possono trasformarsi l'una nell'altra. Pre-elaborati con il dizionario e prima di iniziare la ricerca controlla se le due parole finali si trovano nello stesso gruppo connesso. La pre-elaborazione richiederà solo un tempo proporzionale al numero di transizioni valide da parola a parola, quindi puoi farla franca ogni volta che carichi il dizionario. Dovresti memorizzare l'ID di gruppo di ogni parola, in modo da richiedere un po 'più di spazio.