[leetcode]243.最短单词距离

[MagicalBridge]

给定一个单词列表和两个单词 word1 和 word2，返回列表中这两个单词之间的最短距离。

示例:

假设 words = ["practice", "makes", "perfect", "coding", "makes"]

输入: word1 = “coding”, word2 = “practice”
输出: 3

输入: word1 = "makes", word2 = "coding"
输出: 1

注意:
你可以假设 word1 不等于 word2, 并且 word1 和 word2 都在列表里。

解法
这是一个非常直接的编程题目，i1和i2两个位置距离为|i1 - i2| 为了找到 word1 和 word2 我们需要遍历输入的数组并找到i1和i2在数组中出现的位置，并检查 |i1-i2| 是否比目前记录的最小值要小。

方法1：暴力解法

算法

一个比较简单的方法就是遍历整个数组直到找到第一个单词，每次我们找到跟第一个单词一样的词时候，我们就遍历整个数组去寻找第二个单词一样的词，并求出最近的距离。

/**
 * @param {string[]} words
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var shortestDistance = function (words, word1, word2) {
  // 初始化设置距离为数组的长度
  let minDistance = words.length;
  for (let i = 0; i < words.length; i++) {
    // 找到第一个单词
    if (words[i] === word1) {
      // 继续在数组中寻找第二个单词
      for (let j = 0; j < words.length; j++) {
        if (words[j] === word2) {
          minDistance = Math.min(minDistance, Math.abs(i - j))
        }
      }
    }
  }
  return minDistance;
};

复杂度分析

• 时间复杂度：O(n)O(n) 。这个问题的解法是线性的，我们无法比 O(n)O(n) 更快是因为我们至少要遍历每个元素一次。
• 空间复杂度：O(1)O(1) 。没有使用额外空间。