2eBFS JavaScript solution


  • 0
    L

    from is used to keep the parent node so it is easier to rebuild path when there is conjunction between src and dst

    function findLadders(beginWord, endWord, wordList) {
        var src = new Set([beginWord]);
        var dst = new Set([endWord]);
        
        wordList.delete(beginWord);
        wordList.delete(endWord);
        
        var from = {};
        var res = [];
        
        while (src.size && dst.size) {
            if (src.size > dst.size) [src, dst] = [dst, src];
            
            var newSet = new Set();
            
            for (var w of src) {
                var arr = w.split('');
                
                for (var i = 0; i < arr.length; i++) {
                    for (var j = 0; j < 26; j++) {
                        arr[i] = String.fromCharCode(97 + j);
                        
                        if (arr[i] === w[i]) continue;
                        
                        var newWord = arr.join('');
                        
                        if (dst.has(newWord)) buildPath(w, [w, newWord], newWord, 0);
                        
                        if (wordList.has(newWord)) {
                            newSet.add(newWord);
                            from[newWord] = from[newWord] || [];
                            from[newWord].push(w);
                        }
                        
                        arr[i] = w[i];
                    }
                }
            }
            
            if (res.length) return res;
            
            newSet.forEach(w => wordList.delete(w));
            src = newSet;
        }
        
        return [];
        
        function buildPath(s, path, d) {
            if (!from[s] && !from[d]) {
                return res.push(path[0] === beginWord ? path.slice() : path.slice().reverse());
            }
            
            if (from[s]) {
                from[s].forEach(w => buildPath(w, [w, ...path], d));
            } else {
                from[d].forEach(w => buildPath(s, [...path, w], w));
            }
        }
    }

Log in to reply
 

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