【Day 30】面试题 17.11. 单词距离

题目描述

有个内含单词的超大文本文件，给定任意两个单词，找出在这个文件中这两个单词的最短距离(相隔单词数)。如果寻找过程在这个文件中会重复多次，而每次寻找的单词不同，你能对此优化吗?

示例：

输入：words = ["I","am","a","student","from","a","university","in","a","city"], word1 = "a", word2 = "student" 输出：1 提示：

words.length <= 100000

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-closest-lcci 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的回答

解法一

时间复杂度 O(n^2) 最复杂的情况(n/2)^2?

空间复杂度 O(n) 最长应该也就一个 n 的空间

var findClosest = function (words, word1, word2) {
    let wordArr = []
    let word2Arr = []
    for (let i = 0; i < words.length; i++) {
        if (words[i] === word1) wordArr.push(i)
        if (words[i] === word2) word2Arr.push(i)
    }
    let short = Infinity
    for (let i of wordArr) {
        for (let j of word2Arr) {
            short = Math.min(short, Math.abs(i - j))
        }
    }
    return short
};

解法二

时间复杂度 O(n) 一个循环

空间复杂度 O(1) 三个参数空间

奇怪了，怎么还没第一个跑得快

var findClosest = function (words, word1, word2) {
    let word1Pos = 0
    let word2Pos = 0
    let short = Infinity
    for (let i = 0; i < words.length; i++) {
        if (words[i] === word1) word1Pos = i
        if (words[i] === word2) word2Pos = i
        if (word1Pos && word2Pos) short = Math.min(short, Math.abs(word1Pos - word2Pos))
        if (short <= 1) break
    }
    return short
};

参考回答

前置知识

• 哈希
• 空间换时间
• 双指针

两个数组

思路

一个简单的思路是：分别找出 word1 和 word2 在 words 中的所有出现的索引 ids1 和 ids2。于是问题转换为：从两个有序数组分别选一个数，使得二者差的绝对值最小。

代码

代码支持: Python

Python Code:

class Solution:
    def findClosest(self, words: List[str], word1: str, word2: str) -> int:
        # [2,5,8]
        ids1 = []
        # [3]
        ids2 = []
        ans = len(words)

        for i in range(len(words)):
            if words[i] == word1:
                ids1.append(i)
            if words[i] == word2:
                ids2.append(i)
        i = j = 0
        while i < len(ids1) and j < len(ids2):
            if ids1[i] < ids2[j]:
                ans = min(ans, ids2[j] - ids1[i])
                i += 1
            else:
                ans = min(ans, ids1[i] - ids2[j])
                j += 1

        return ans

复杂度分析

• 时间复杂度：$O(N)$，其中 N 为 words 的长度。
• 空间复杂度：$O(N)$，其中 N 为 words 的长度。

双指针

思路

实际上，上面的数组是没有必要的。我们可以边遍历边计算，从而在 One Pass 内完成，并且只占用常数空间。

代码

代码支持: Python, C++

Python Code:

class Solution:
    def findClosest(self, words: List[str], word1: str, word2: str) -> int:
        ans = len(words)
        id1 = id2 = -1
        for i in range(len(words)):
            if words[i] == word1:
                id1 = i
            if words[i] == word2:
                id2 = i
            if id1 != -1 and id2 != -1:
                ans = min(ans, abs(id1 - id2))
        return ans

C++ Code:

class Solution {
    public:
    int findClosest(vector < string > & words, string word1, string word2) {

        int id1 = -1, id2 = -1, ans = words.size()
        for (int i=0
             i < words.size()
             i + +) {
            if (words[i] == word1) id1 = i
            if (words[i] == word2) id2 = i
            if (id1 != -1 && id2 != -1) ans = min(ans, abs(id1 - id2))
        }
        return ans
    }
}

复杂度分析

• 时间复杂度：$O(N)$，其中 N 为 words 的长度。
• 空间复杂度：$O(1)$