Javascript, beats 100%, BFS + keep record of words' path


  • 0
    C

    A better space complexity can be achieved by only keeping the record of each's word's previous word. This solution keeps a record of each word's entire path for the sake of clarity.

    var findLadders = function (beginWord, endWord, wordList) {
        let layers = [], layers2 = [], ans = [], nextLayer, dict1, dict2,
            wordList2 = new Set(wordList), foundAns = [];
        wordList.delete(beginWord); wordList.add(endWord); wordList2.delete(endWord); wordList2.add(beginWord);
        layers[0] = [{path: [], word: beginWord}]; layers2[0] = [{path:[], word: endWord}];
        
        while (layers[layers.length-1].length>0 && layers2[layers2.length-1].length>0) {
            let thisLayers;
            if (layers[layers.length-1].length <= layers2[layers2.length-1].length){
                thisLayers = layers;
                dict1 = wordList; dict2 = wordList2;
            } else {
                thisLayers = layers2;
                dict1 = wordList2; dict2 = wordList;
            }
            nextLayer = [];
            
            for (let i = 0; i < thisLayers[thisLayers.length - 1].length; i++) {
                getNextWords(thisLayers[thisLayers.length - 1][i], i);
            }
            thisLayers[thisLayers.length] = nextLayer;
            //Check if answer is found in this layer
            if (foundAns.length>0){
                foundAns = foundAns.sort((a,b)=>{return a.localeCompare(b)});
                for (let k=0;k<foundAns.length;k++){
                    while (k!==0 && foundAns[k]===foundAns[k-1]) k++;
                    let indexArr1 = [], indexArr2 = [];
                    let l1 = layers.length-1, l2 = layers2.length-1;
                    for (let l=0;l<layers[l1].length;l++) {if (foundAns[k]===layers[l1][l].word) indexArr1[indexArr1.length] = l}
                    for (let l=0;l<layers2[l2].length;l++) {if (foundAns[k]===layers2[l2][l].word) indexArr2[indexArr2.length] = l}
                    
                    for (let j1=0;j1<indexArr1.length;j1++){
                        for (let j2=0;j2<indexArr2.length;j2++){
                            let index1 = indexArr1[j1], index2 = indexArr2[j2];
                            ans[ans.length] = layers[l1][index1].path.concat(foundAns[k], layers2[l2][index2].path.slice(0).reverse());
                        }
                    }
                }
                
                return ans;
            }
            for (let k=0;k<nextLayer.length;k++) dict1.delete(nextLayer[k].word);
        }
        return [];
        
        function getNextWords(wordNode, index) {
            let chars = "abcdefghijklmnopqrstuvwxyz";
            
            for (let i=0;i<wordNode.word.length;i++){
                for (let j=0; j<chars.length;j++){
                    let temp = wordNode.word.slice(0, i) + chars[j] + wordNode.word.slice(i+1);
                    if (dict1.has(temp)) {
                        if (!dict2.has(temp)) {
                            foundAns[foundAns.length] = temp;
                        }
                        let newPath = wordNode.path.slice(0); newPath[newPath.length] = wordNode.word;
                        nextLayer[nextLayer.length] = {path: newPath, word: temp};
                    }
                }
            }
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.