Force deduction solution summary interview question 17.11- word distance

  Directory links ：

Force buckle programming problem - The solution sums up _ Share + Record -CSDN Blog

GitHub Synchronous question brushing items ：

https://github.com/September26/java-algorithms

Original link ： Power button

describe ：

There's a huge text file with words , Given any two different words , Find the shortest distance between the two words in this file ( Number of words separated ). If the search process is repeated many times in this file , And each time I look for a different word , Can you optimize this ?

Example ：

Input ：words = ["I","am","a","student","from","a","university","in","a","city"], word1 = "a", word2 = "student"
Output ：1
Tips ：

words.length <= 100000

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/find-closest-lcci
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
*  Traverse words, Add to map among .key For the word ,value For inheritance , Store the position corresponding to the word .
*  lookup word1 and word2 At the shortest distance between , Find two corresponding sets , Find the minimum difference between two sets .

Code ：

public class SolutionMST1711 {

    public int findClosest(String[] words, String word1, String word2) {
        Map<String, List<Integer>> map = new HashMap<>();

        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            List<Integer> integers = map.get(word);
            if (integers == null) {
                integers = new ArrayList<>();
                map.put(word, integers);
            }
            integers.add(i);
        }

        List<Integer> integers1 = map.get(word1);
        List<Integer> integers2 = map.get(word2);

        Collections.sort(integers1);
        Collections.sort(integers2);

        int minDiff = Integer.MAX_VALUE;
        int index1 = 0;
        int index2 = 0;
        while (index1 < integers1.size() && index2 < integers2.size()) {
            int integer1 = integers1.get(index1);
            int integer2 = integers2.get(index2);
            minDiff = Math.min(minDiff, Math.abs(integer1 - integer2));
            if (integer1 >= integer2) {
                index2++;
                continue;
            }
            index1++;
        }
        return minDiff;
    }
}