JavaScript solution


  • 1
    A
    /**
     * @constructor
     * @param {string[]} words
     */
    function WordDistance(words) {
      this.words = words;
      
      // map words to their indexes in an array
      this.indexes = words
        .reduce((map, word, i) => {
          map[word] = (map[word] || []).concat(i);
    
          return map;
        }, {});
    }
    
    /**
     * @param {string} word1
     * @param {string} word2
     * @return {integer}
     */
    WordDistance.prototype.shortest = function(word1, word2) {
      const xs = this.indexes[word1];
      const ys = this.indexes[word2];
    
      let min = Infinity;
    
      for (let x of xs) {
        for (let y of ys) {
          min = Math.min(min, Math.abs(y - x));
        }
      }
    
      return min;
    };
    
    /***
    Alternatively, using `reduce`:
    
    WordDistance.prototype._shortest = function(word1, word2) {
      return this.indexes[word1].reduce((min, x) => {
        return this.indexes[word2].reduce((_min, y) => {
          return Math.min(_min, Math.abs(y - x));
        }, min);
      }, Infinity);
    };
    
    ***/
    

  • 0
    Y

    Hi
    I have the similar solution, but it can be better. In your shortest function, when you compare y and x, you can jump out of the inner loop when y > x, since it makes no sense to continue if y is already larger than x.
    min = Math.min(min, Math.abs(y - x));
    if (y > x) break;


  • 0
    Y

    Just want to update. Previous solution is O(n^2) time complicity (please correct me if I was wrong), there is an O(n) solution for shortest function. Since arr1 and arr2 is already sorted, we can use merge solution to avoid two for loops.

    /**

    • @param {string} word1
    • @param {string} word2
    • @return {integer}
      */
      WordDistance.prototype.shortest = function(word1, word2) {
      var arr1 = map[word1];
      var arr2 = map[word2];
      var res = Number.MAX_VALUE, i=0, j=0;
      while (i<arr1.length && j<arr2.length) {
      res = Math.min(res, Math.abs(arr1[i] - arr2[j]));
      if (arr1[i] > arr2[j]) j++;
      else i++;
      }
      return res;
      };

Log in to reply
 

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