侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【遍历, 模拟】单词距离

GabrielxD
2022-05-26 / 0 评论 / 0 点赞 / 33 阅读 / 723 字 / 正在检测是否收录...

题目

面试题 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 更新为 currprevIdx 更新为 i
  • 同理,如果当前遍历到的单词与 word2 相同,上一个符合条件的单词(prev)是 word1,说明这对单词是一组合法解,把它们的索引作差更新距离最小值。
    然后把 prev 更新为 currprevIdx 更新为 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,如果这次遍历中 ptr1ptr2 都是有效值,就取其作差的绝对值更新 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;
    }
}

剪枝优化

如果某次循环中 ptr1ptr2 都没被更新,那么作差也不会变,ans 也不会被跟新,直接进行下一次循环即可,如果 ans==1 说明 word1word2 出现位置已经相邻了,距离再小也不会小过 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;
    }
}
0

评论区