Ich versuche, einen Algorithmus zu codieren, der den kürzesten Transformationspfad von einem bestimmten beginWord zu einem endWord finden soll, sodass jeweils ein Buchstabe geändert werden kann.

Testfall

beginWord = "hit"

endWord = "cog"

wordList = ["hot","dot","dog","lot","log","cog"]

Die erwartete Ausgabe ist 5, da eine der kürzesten Transformationen folgen kann, deren Länge 5 beträgt:

"hit" -> "hot" -> "dot" -> "dog" -> "cog"

In meinem Algorithmus folge ich BFS mithilfe der Warteschlange und ersetze für jedes Wort jeden Buchstaben durch alle Alphabete von 'a' bis 'z'. Dabei überprüfe ich, ob das resultierende Wort im angegebenen Wörterbuch vorhanden ist, dh das Wortliste .

Wenn ja, dann schiebe ich es in die Warteschlange, damit es genauso wie das letzte Wort verarbeitet werden kann. Andernfalls wird der nächste Eintrag aus der Warteschlange usw. vorgenommen, bis die Warteschlange leer ist.

Mein unten angegebener Code gibt nun hit -> hot -> dot -> lot -> dog -> log -> cog zurück, was eine falsche Ausgabe ist. Dies liegt hauptsächlich an der falschen Umwandlung von dot in lot sowie dog.

Sowohl lot als auch dog und ein Buchstabe, der sich von dot unterscheidet, werden daher beide in die Warteschlange gestellt und später verarbeitet, was zu einem ähnlichen Problem der doppelten Transformation von lot in {führt {X4}} und cog.

Dies zeigt deutlich, dass mir ein entscheidender Punkt der BFS und der Suche nach kürzesten Wegen fehlt. Wie kann ich entscheiden, dass ich dot in dog anstelle von lot umwandeln muss, um sicherzustellen, dass ich auf einem kürzesten Weg zum erwarteten Ziel komme, vorausgesetzt, beide sind gültige Transformationen von dot.

Dies wird mir helfen, meinen Code zu verstehen und zu korrigieren.

var ladderLength = function(beginWord, endWord, wordList) {

    wordList = new Set(wordList);
    var str = [beginWord];

    var queue = [], distance = 0, i, j, len;
    len = beginWord.length;
    queue.push(beginWord);

    while (queue.length > 0) {
        var currentWord = queue.shift();
        if (currentWord === endWord) {
            console.log(str.join(" -> "));
            return distance + 1;
        }
        for (i = 0; i < len; i++) {
            var tempCh = currentWord[i];
            for (j = 'a'; j <= 'z'; j = String.fromCharCode(j.charCodeAt(0)+1)) {
                currentWord = currentWord.replaceAt(i,j);
                if (wordList.has(currentWord)) {
                    distance++;
                    wordList.delete(currentWord);
                    str.push(currentWord);
                    queue.push(currentWord);
                }
            }
            currentWord = currentWord.replaceAt(i, tempCh);

        }   
    }
    return 0;
};


String.prototype.replaceAt=function(index, replacement) {
    return this.substr(0, index) + replacement+ this.substr(index + replacement.length);
}
1
Usman 18 Apr. 2018 im 08:32

3 Antworten

Beste Antwort

Ich glaube, ich habe das Hauptproblem in meinem Verständnis gefunden. Das Hauptproblem bestand darin, dass ich auf einer gegebenen Ebene, die der Abstand 'd' von der Wurzelebene des Baums ist, mehrere Übereinstimmungen haben kann, z. "Los" und "Hund" waren auf dem gleichen Niveau wie durch Transformation von "Punkt".

Auf jeder Ebene muss ich die Warteschlange erschöpfen, da sonst die von mir berechnete Entfernung falsch wird.

Als ich meinen Code wie folgt änderte (siehe Kommentar Process all items in queue which contains words on same level im Code), wurde der Algorithmus besser. Besser zumindest für viele Testfälle, einschließlich des in dieser Frage angegebenen.

Vielen Dank, dass Sie den Code überprüft haben. :) :)

Var ladderLength = Funktion (beginWord, endWord, wordList) {wordList = new Set (wordList);

    var queue = [], distance = 1, i, j, len;
    len = beginWord.length;
    queue.push(beginWord);

    while (queue.length > 0) {
        // Process all items in queue which contains words on same level
        for (var k=0; k<queue.length; k++) {
            var currentWord = queue.shift();
            if (currentWord === endWord) {
                return distance;
            }

            for (i = 0; i < len; i++) {
                var tempCh = currentWord[i];
                for (j = 'a'; j <= 'z'; j = String.fromCharCode(j.charCodeAt(0)+1)) {
                    if (j !== tempCh) {
                        currentWord = currentWord.replaceAt(i,j);
                        if (wordList.has(currentWord)) {
                            wordList.delete(currentWord);
                            queue.push(currentWord);
                        }
                    }
                }
                currentWord = currentWord.replaceAt(i, tempCh);

            } 
        }
        distance++;
    }
    return 0;
};

String.prototype.replaceAt=function(index, replacement) {
    return this.substr(0, index) + replacement+ this.substr(index + replacement.length);
}
0
Usman 20 Apr. 2018 im 06:57

Sie können zusätzliche Änderungen vornehmen, während Sie die Zeichenfolge transformieren, um die richtige Ausgabe zu erhalten. Vergleichen Sie vor dem Ersetzen des Buchstabens das Zeichen, das ersetzt werden soll (i) mit dem Zeichen, das an seine Stelle tritt (j).

Behalten Sie für jede Iteration eine Flag-Variable flag bei und prüfen Sie, ob das neue Zeichen j näher an dem Zeichen an der entsprechenden Position in EndWord liegt. Wenn es näher kommt, anstatt wegzugehen (z. B. 'd' vs 'l' für 'c' im Zahnrad) und in WordList vorhanden ist, nehmen Sie den Ersatz vor und setzen Sie flag = true. Wenn mit der gleichen Entfernung vom Zeichen auch eine andere Transformation möglich ist, suchen Sie nach dem Flag. Wenn dies der Fall ist, überspringen Sie es, andernfalls führen Sie die Transformation durch.

Hoffe das hilft.

0
Akash Srivastav 18 Apr. 2018 im 06:09

Ich ersetze jeden Buchstaben durch alle Buchstaben


bedeutet, dass Sie viel zu viele Gültigkeitsprüfungen durchführen.
Ich schlage vor, dass Sie jeden Buchstaben nur durch gültige Buchstaben ersetzen. Zum Beispiel kann ich in "hit" nur durch o von "hot", "dot", "dog", "lot", "log", "cog" ersetzt werden.
Dadurch wird das Programm effizienter und weniger fehleranfällig.

0
c0der 20 Apr. 2018 im 07:36