Simple JavaScript solution using map of sorted positions


  • 0
    var WordDistance = function(words) {
        this.positions = {};
        for (let i = 0; i < words.length; i++) {
            this.positions[words[i]] = this.positions[words[i]] || [];
            this.positions[words[i]].push(i);
        }
        for (let key in this.positions) {
            this.positions[key].sort((a, b) => a - b);
        }
    };
    
    WordDistance.prototype.shortest = function(word1, word2) {
        const pos1 = this.positions[word1];
        const pos2 = this.positions[word2];
        let i = 0, j = 0, min = Infinity;
        while (true) {
            min = Math.min(min, Math.abs(pos1[i] - pos2[j]));
            if (pos1[i] < pos2[j]) {
                if (i++ === pos1.length - 1) return min;
            } else {
                if (j++ === pos2.length - 1) return min;
            }
        }
    };
    

    Sorting the positions allows us to return shortest slightly early, with a small sacrifice in build time (O(n log k) when word frequency k is close to uniform).


Log in to reply
 

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