Shortest Word Distance 类

Shortest Word Distance

数组内单词可能有重复，所以需要在 word1 & word2 的多次出现位置中，寻找最近的。

用一些数组的小 trick，比如 index = -1 作为 “还没找到” 的初始化条件，而两个指针所保存的，都是 word1 / word2 所最近出现的位置，one-pass 即可。

public class Solution {
    public int shortestDistance(String[] words, String word1, String word2) {
        int minDis = Integer.MAX_VALUE;
        int oneIndex = -1, twoIndex = -1;

        for(int i = 0; i < words.length; i++){
            if(words[i].equals(word1)) oneIndex = i;
            if(words[i].equals(word2)) twoIndex = i;

            if(oneIndex != -1 && twoIndex != -1) 
                minDis = Math.min(minDis, Math.abs(oneIndex - twoIndex));
        }
        return minDis;
    }
}

Shortest Word Distance II

这样的问题设计方式实在提醒自己问清楚问题要求，比如 wordList 大小，是否有重复，函数调用次数是否频繁等等。这题在原先基础上增加了 data structure API 调用的考量。

思路很简单，调用多次之后每次再去重新扫很不经济，需要数据结构去存储每个 word 出现的位置，每次 API 调用时直接在两个 list 中找最小距离。

比较两个 list 的方法类似窗口型双指针的基本思想：虽然双指针所能组成的 pair 数量是 n^2，但是对于指定位置的 ptr，我们可以证明后面的所有 pair 组合都是没有意义的，因此可以把指针单向移动。

public class WordDistance {
    HashMap<String, List<Integer>> map;
    public WordDistance(String[] words) {
        map = new HashMap<String, List<Integer>>();

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

    public int shortest(String word1, String word2) {
        List<Integer> oneList = map.get(word1);
        List<Integer> twoList = map.get(word2);

        int ptr1 = 0, ptr2 = 0;
        int minDis = Integer.MAX_VALUE;

        while(ptr1 < oneList.size() && ptr2 < twoList.size()){
            minDis = Math.min(minDis, Math.abs(oneList.get(ptr1) - twoList.get(ptr2)));
            if(oneList.get(ptr1) < twoList.get(ptr2)){
                ptr1 ++;
            } else {
                ptr2 ++;
            }
        }

        return minDis;
    }
}

Shortest Word Distance III

改成 word1 有可能等于 word2 之后，这题的重点就变成了各种 corner case 怎么处理，比如

【"a","c","a","a"】, word1 = "a", word2 = "a"

【"a", "a"】, word1 = "a", word2 = "a"

换句话讲，就是看你能否考虑到各种情况正确地 assign index.

public class Solution {
    public int shortestWordDistance(String[] words, String word1, String word2) {
        int ptr1 = -1, ptr2 = -1;
        boolean isSame = word1.equals(word2);
        int minDis = Integer.MAX_VALUE;

        for(int i = 0; i < words.length; i++){
            if(words[i].equals(word1)){
                if(isSame){
                    ptr1 = ptr2;
                    ptr2 = i;
                } else {
                    ptr1 = i;
                }
            } else if(words[i].equals(word2)){
                ptr2 = i;
            }

            if(ptr1 != -1 && ptr2 != -1) minDis = Math.min(minDis, Math.abs(ptr1 - ptr2));
        }

        return minDis;
    }
}