shortest-word-distance-ii

• Medium
• keyword: map
• 类似: 2 sum closest

For example, Assume that words = ["practice", "makes", "perfect", "coding", "makes"]. Given word1 = “coding”, word2 = “practice”, return 3. Given word1 = "makes", word2 = "coding", return 1.

思路

• 建立一个map: 找到string->list(index).

• 然后对于每2个word, 找最接近的index. 这道题目的关键是怎么找最近的距离?

  • 什么是最近的距离? 例如word1的list是: [1,3,9], word2的list是: [5,10]. 那么最近的距离是[9,10], 即1. 即abs(a[i], b[j])最小. 这个怎么找? 于是问题转化为2个排好序的数组, 找最小差值.

• 最直接的想法自然是: O(m*n), 即对2个for loop, outer loop处理list1, inner loop处理list2.

• 想到2Sum closest的O(m+n)做法. 不过有点区别:

  • 它那个是l=0, r=n-1, 因为从大缩到小.

  • 这里是找最接近的, 所以p1 = 0, p2 = 0. 但这样不会导致while(p1<list1.length && p2.list2.length)提前退出吗? Ans: 并不会, 因为对于递增的处理是这样的:

    while(p1<list1.length && p2.list2.length) {
      if (diff < abs(list1[p1] - list2[p2])) {
          diff = abs(list1[p1] - list2[p2])
      }
      if (list1[p1] < list2[p2]) {
          p1++;
      }
      else {
          p2++;
      }
    }