Leetcode 127

This problem is a review of the algorithm encountered the most complex, the previous several times encountered this is just copy, this time to this problem solution to make a note, in understanding.

127. The word solitaire is difficult

Topic describes

The conversion sequence from beginWord to endWord in the dictionary wordList is a sequence formed according to the following specification: the first word in the sequence is beginWord. The last word in the sequence is endWord. Only one letter can be changed per conversion. The intermediate word in the conversion process must be a word in the dictionary wordList. Given two words beginWord and endWord and a dictionary wordList, find the number of words in the shortest conversion sequence from beginWord to endWord. If no such conversion sequence exists, return 0. Example 1: Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] output: 5 A minimum conversion sequence is "hit" - > "hot" - > "dot" - > "dog" - > "cog", return it the length of 5. Example 2: Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] Output: 0 EndWord "cog" is not in the dictionary, so it cannot be converted. Tip:  1 <= beginWord.length <= 10 endWord.length == beginWord.length 1 <= wordList.length <= 5000 wordList[i].length == BeginWord. Length beginWord, endWord and wordList[I] consists of lowercase Letters beginWord! = All strings in the endWord wordList are differentCopy the code

Solution: Some notes are in the comments

1. The shortest sequence traversal path is always the first

var ladderLength = function (beginWord, endWord, wordList) {
    if(! endWord || ! wordList.includes(endWord)) {return 0;
    }
    
    // Change a character of a word to * to find the corresponding large force
    var comboDicts = {};

    var len = beginWord.length;
    for (let i = 0; i < wordList.length; i++) {
        for (let r = 0; r < len; r++) {
            var newWord =
                wordList[i].substring(0, r) + "*" + wordList[i].substring(r + 1, len);
            !comboDicts[newWord] && (comboDicts[newWord] = []);
            comboDicts[newWord].push(wordList[i]);
        }
    }


    var queue = [[beginWord, 1]].// The registration that will appear
    var visited = { [beginWord]: true };
    while (queue.length) {
        var currNode = queue.shift();
        var currWord = currNode[0];
        var currLevel = currNode[1];

        for (let i = 0; i < len; i++) {
        
            var newWord =
                currWord.substring(0, i) + "*" + currWord.substring(i + 1, len);
            
            // Find a sibling
            if (newWord in comboDicts) {
                var tempWords = comboDicts[newWord];
                
                for (let z = 0; z < tempWords.length; z++) {
                    // See if there are any final results among our compatriots
                    if (tempWords[z] == endWord) {
                        return currLevel + 1;
                    }
                    
                    // Register the sibling
                    if(! visited[tempWords[z]]) { visited[tempWords[z]] =true;
                        // See if the sibling can find the final result after the change
                        queue.push([tempWords[z], currLevel + 1]);
                    }
                }
            }
        }
    }
    return 0;
};
Copy the code

Solution two uses es6 syntax

var ladderLength = function (beginWord, endWord, wordList) {
    let wordListSet = new Set(wordList);
    if(! wordListSet.has(endWord))return 0;

    let beginSet = new Set(a); beginSet.add(beginWord);let endSet = new Set(a); endSet.add(endWord);let level = 1;

    while (beginSet.size) {
        let nextBeginSet = new Set(a);for (let key of beginSet) {
            for (let i = 0; i < key.length; i++) {
                for (let j = 0; j < 26; j++) {
                    let s = String.fromCodePoint(97 + j);
                    if(s ! = key[i]) {let newWord = key.slice(0, i) + s + key.slice(i + 1);

                        if (endSet.has(newWord)) {
                            return level + 1;
                        }

                        if (wordListSet.has(newWord)) {
                            nextBeginSet.add(newWord);
                            wordListSet.delete(newWord);
                        }
                    }
                }
            }
        }
        beginSet = nextBeginSet;
        level++;
        if(beginSet.size > endSet.size) { [beginSet, endSet] = [endSet, beginSet]; }}return 0;
};
Copy the code

This article referred to qin shi Mingyue’s solution, originally looked at some of the Java solution but some of the syntax is not too familiar, or cut back to js 😄