单词距离

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

示例：

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

words.length <= 100000
通过次数9,203提交次数13,417

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

使用双指针去找目标词：

• 当 指针 l 找到 word1 时，指针 r 从 指针 l 的右边出发去找 word1 或者 word2；

• 如果 指针 r 找到了 word2，计算距离 r - l，同时记录一个最小的距离；

• 如果 指针r找到的还是 word1，更新 指针 l 到 指针 r 的位置，指针r 继续右移寻找；

  作者：suukii
  链接：https://leetcode-cn.com/problems/find-closest-lcci/solution/mian-shi-ti-1711dan-ci-ju-chi-shuang-zhi-zhen-ha-x/
  来源：力扣（LeetCode）
  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
    public int findClosest(String[] words, String word1, String word2) {
        int left = words.length - 1;
        int min = Integer.MAX_VALUE;

        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(word2)) {
                left = i;
            }

            if (words[i].equals(word1)) {
                int right = -1;
                if (Math.abs(i - left) <= 1) return 1;
                for (int j = i + 1; j < words.length; j++) {
                    if (words[j].equals(word2)) {
                        right = j;
                        break;
                    }
                }
                if (right == -1) {
                    min = Math.min(Math.abs(i - left), min);
                } else {
                    min = Math.min(Math.min(Math.abs(i - left), Math.abs(right - i)), min);
                }
            }
        }
        return min;

    }
}

多次查询构建哈希表

class Solution {
    public int findClosest(String[] words, String word1, String word2) {
        HashMap<String,List<Integer>> map = new HashMap<>();
        //构造哈希表
        for(int i=0;i<words.length;i++){
            List<Integer> list = map.getOrDefault(words[i],new ArrayList<>());
            list.add(i);
            map.put(words[i], list);
        }
        List<Integer> l1 = map.get(word1);
        List<Integer> l2 = map.get(word2);
        int i=0;
        int j=0;
        int min = Integer.MAX_VALUE;
        while(i<l1.size()&&j<l2.size()){
            int curr1 = l1.get(i);
            int curr2 = l2.get(j);
            min = Math.min(min,Math.abs(curr1-curr2));
            if(curr1<curr2){
                i++;
            }else{
                j++;
            }
        }
        return min;
    }
}

作者：ppppjcute
链接：https://leetcode-cn.com/problems/find-closest-lcci/solution/java-gen-ju-duo-ci-cha-xun-you-hua-by-ppppjqute/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信