【遍历, 模拟】单词距离

题目

面试题 17.11. 单词距离

---

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

示例：

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

提示：

• words.length <= 100000

解题

方法一：遍历 模拟

思路

遍历字符串数组：

• 如果当前遍历到的单词与 word1 相同，上一个符合条件的单词(prev)是 word2，说明这对单词是一组合法解，把它们的索引作差更新距离最小值。
  然后把 prev 更新为 curr，prevIdx 更新为 i。
• 同理，如果当前遍历到的单词与 word2 相同，上一个符合条件的单词(prev)是 word1，说明这对单词是一组合法解，把它们的索引作差更新距离最小值。
  然后把 prev 更新为 curr，prevIdx 更新为 i。

代码

class Solution {
    public int findClosest(String[] words, String word1, String word2) {
        int len = words.length;
        String prev = "";
        int prevIdx = 0;
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < len; i++) {
            String curr = words[i];
            if (curr.equals(word1)) {
                if (prev.equals(word2)) ans = Math.min(ans, i - prevIdx); 
                prev = curr;
                prevIdx = i;
            } else if (curr.equals(word2)) {
                if (prev.equals(word1)) ans = Math.min(ans, i - prevIdx); 
                prev = curr;
                prevIdx = i;
            }
        }
        return ans;
    }
}

优化

不用记录上一个符合要求的单词，在遍历的过程中始终记录最新遇到的符合要求的单词的索引，如果遇到了 word1 就更新 ptr1，如果遇到 word2 就更新 ptr2，如果这次遍历中 ptr1 和 ptr2 都是有效值，就取其作差的绝对值更新 ans ，保证 ans 最小。

class Solution {
    public int findClosest(String[] words, String word1, String word2) {
        int len = words.length, ans = len;
        for (int i = 0, ptr1 = -1, ptr2 = -1; i < len; i++) {
            String curr = words[i];
            if (curr.equals(word1)) ptr1 = i;
            else if (curr.equals(word2)) ptr2 = i;
            if (ptr1 != -1 && ptr2 != -1) {
                ans = Math.min(ans, Math.abs(ptr1 - ptr2));
            }
        }
        return ans;
    }
}

剪枝优化

如果某次循环中 ptr1 和 ptr2 都没被更新，那么作差也不会变，ans 也不会被跟新，直接进行下一次循环即可，如果 ans==1 说明 word1 和 word2 出现位置已经相邻了，距离再小也不会小过 1 直接返回结果 1 即可。

class Solution {
    public int findClosest(String[] words, String word1, String word2) {
        int len = words.length, ans = len;
        for (int i = 0, ptr1 = -1, ptr2 = -1; i < len; i++) {
            String curr = words[i];
            if (curr.equals(word1)) ptr1 = i;
            else if (curr.equals(word2)) ptr2 = i;
            else continue;
            if (ptr1 != -1 && ptr2 != -1) {
                ans = Math.min(ans, Math.abs(ptr1 - ptr2));
            }
            if (ans == 1) return ans;
        }
        return ans;
    }
}