244. Shortest Word Distance II

最短单词距离

• 时间复杂度O(n)，空间复杂度O(n)
• Runtime: 112 ms, faster than 79.09%
• Memory Usage: 46.5 MB, less than 47.53%

/**
 * @param {string[]} wordsDict
 */
var WordDistance = function(wordsDict) {
  this.map = new Map();
  for (let i = 0; i < wordsDict.length; i++) {
    const val = wordsDict[i];
    if (!this.map.has(val)) {
      this.map.set(val, []);
    }
    const cur = this.map.get(val);
    cur.push(i);
    this.map.set(val, cur);
  }
};

/** 
 * @param {string} word1 
 * @param {string} word2
 * @return {number}
 */
WordDistance.prototype.shortest = function(word1, word2) {
  const index1 = this.map.get(word1);
  const index2 = this.map.get(word2);
  let i1 = 0;
  let i2 = 0;
  let min = Number.MAX_VALUE;
  while (i1 < index1.length && i2 < index2.length) {
    min = Math.min(min, Math.abs(index1[i1] - index2[i2]));
    if (index1[i1] > index2[i2]) {
      i2++;
    } else {
      i1++
    }
  }
  return min;
};

/** 
 * Your WordDistance object will be instantiated and called as such:
 * var obj = new WordDistance(wordsDict)
 * var param_1 = obj.shortest(word1,word2)
 */