小鲸鱼的梦境
0%

『LeetCode』1000039 单词距离

发表于 分类于 Valine：
本文字数： 3.2k 阅读时长 ≈ 3 分钟

题目

面试题 17.11. 单词距离

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

示例：

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

提示：

  • words.length <= 100000

题解

【单词距离】哈希表&双指针模拟

双指针

一个简单的想法：记录下 word1 和 word2 出现的位置，然后问题就转化为在两个数组中寻找值最接近的数，可以使用双指针求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Code language: Python
class Solution:
    def findClosest(self, words: List[str], word1: str, word2: str) -> int:
        w1, w2 = list(), list()
        for i, j in enumerate(words):
            if j == word1:
                w1.append(i)
            elif j == word2:
                w2.append(i)
        ans = abs(w1[0] - w2[0])
        n1, n2 = len(w1), len(w2)
        i, j = 0, 0
        while i < n1 and j < n2:
            if j == n2 - 1 or (w1[i] < w2[j]):
                i += 1
            else:
                j += 1
            if i < n1 and j < n2:
                ans = min(ans, abs(w1[i] - w2[j]))
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Code language: Cpp
class Solution {
public:
    int findClosest(vector<string>& words, string word1, string word2) {
        vector<int> w1, w2;
        for (int i = 0, n = words.size(); i < n; ++i) {
            if (words[i] == word1) w1.emplace_back(i);
            else if (words[i] == word2) w2.emplace_back(i);
        }
        int ans = 0x7fffffff;
        for (int i = 0, j = 0, n1 = w1.size(), n2 = w2.size(); i < n1 && j < n2; ) {
            ans = min(ans, w1[i] > w2[j] ? w1[i] - w2[j] : w2[j] - w1[i]);
            if (j == n2 - 1 || (w1[i] < w2[j])) ++i;
            else ++j;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// Code language: Java
class Solution {
    static int[] w1 = new int[100007], w2 = new int[100007];
    public int findClosest(String[] words, String word1, String word2) {
        int p = -1, q = -1;
        for (int i = 0, n = words.length; i < n; ++i) {
            if (words[i].equals(word1)) w1[++p] = i;
            else if (words[i].equals(word2)) w2[++q] = i;
        }
        int ans = 0x7fffffff;
        for (int i = 0, j = 0; i <= p && j <= q; ) {
            ans = Math.min(ans, w1[i] > w2[j] ? w1[i] - w2[j] : w2[j] - w1[i]);
            if (j == q || (w1[i] < w2[j])) ++i;
            else ++j;
        }
        return ans;
    }
}
  • 时间复杂度: \(O(n)\)
  • 空间复杂度: \(O(n)\)

双指针优化

进一步的，无需记录位置，边查找边使用双指针求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
# Code language: Python
class Solution:
    def findClosest(self, words: List[str], word1: str, word2: str) -> int:
        ans = 0x7fffffff
        # a, b 记录两个单词出现的位置
        a, b = -ans, ans
        for i, j in enumerate(words):
            if j == word1:
                a = i
            elif j == word2:
                b = i
            ans = min(ans, abs(a - b))
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
// Code language: Cpp
class Solution {
public:
    int findClosest(vector<string>& words, string word1, string word2) {
        int ans = 0x7fffffff, a = 0x3f3f3f3f, b = 0xf0000000;
        for (int i = 0, n = words.size(); i < n; ++i) {
            if (words[i] == word1) a = i;
            else if (words[i] == word2) b = i;
            ans = min(ans, a > b ? a - b : b - a);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
// Code language: Java
class Solution {
    public int findClosest(String[] words, String word1, String word2) {
        int ans = 0x7fffffff, a = 0x3f3f3f3f, b = 0xf0000000;
        for (int i = 0, n = words.length; i < n; ++i) {
            if (words[i].equals(word1)) a = i;
            else if (words[i].equals(word2)) b = i;
            ans = Math.min(ans, a > b ? a - b : b - a);
        }
        return ans;
    }
}
  • 时间复杂度: \(O(n)\)
  • 空间复杂度: \(O(1)\)

哈希表

若按照题目要求多次调用，那么可以使用哈希表记录所有单词的出现位置，然后再使用双指针求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Code language: Python
class Solution:
    def findClosest(self, words: List[str], word1: str, word2: str) -> int:
        w = defaultdict(list)
        for i, j in enumerate(words):
            w[j].append(i)
        w1, w2 = w[word1], w[word2]
        ans = abs(w1[0] - w2[0])
        n1, n2 = len(w1), len(w2)
        i, j = 0, 0
        while i < n1 and j < n2:
            if j == n2 - 1 or (w1[i] < w2[j]):
                i += 1
            else:
                j += 1
            if i < n1 and j < n2:
                ans = min(ans, abs(w1[i] - w2[j]))
        return ans
  • 时间复杂度: 初始化 \(O(n)\), \(n\) 是 words 的长度，调用 \(O(max(a, b))\), \(a, b\) 分别表示 word1 和 word2 出现的次数
  • 空间复杂度: \(O(n)\)
--- ♥ end ♥ ---

欢迎关注我呀~