Shortest Word Distance 类

Shortest Word Distance

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

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

这道题虽然维护了两个变量, ptr1和ptr2, 实际上却只有一个指针. 这个指针扫过以后, 如果碰到word1, 就set p1, 碰到word2, 就set p2, 可以保证这样的过程不会miss p1与p2的最小差值.

p1_ _ _ p2_ i _ _

p1_ _ _ _ _ _ p2(i)_

_ _ _ _ _ _ _ p2_p1(i)

public class Solution {
    public int shortestDistance(String[] words, String word1, String word2) {
        int p1 = -1; int p2 = -1; int min = Integer.MAX_VALUE;
        for(int i=0;i<words.length;i++){
            if(words[i].equals(word1))
                    p1 = i;
            if(words[i].equals(word2))
                    p2 = i;
            if(p1!=-1 && p2!=-1)
                min = Math.min(min, Math.abs(p1-p2));
        }
        return min;
    }
}

Square面试的时候, onsite第二轮出了一个这道题的变种. 面试官是前google成员, 编了一个google search上的问题. 给了一个字符串, word1, word2, ...word K; 另外给了K个array, array1 里存的是 word1出现的位置[0, 3, 7, ...], array2里存的是word2里出现的位置[2, 9, ...]. 现在求一个coverage array, coverage array包含所有word的index, 保证coverage array里min和max最小. follow up是怎么优化代码, 实际search中怎么建立array. 这道题像是shortest word distance+merge K arraylist的变种

思路: 建立了一个entity<arrayidx, arraycol>, arrayidx代表第k个array, arraycol代表array当前位置. 每次找出arrayidx[arraycol]最小的元素, 只有向前移动这个元素, 才有可能减少coverage. 再找出最大元素求coverage.

Shortest Word Distance II

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

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

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

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

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

    public int shortest(String word1, String word2){
        List<Integer> l1 = map.get(word1);
        List<Integer> l2 = map.get(word2);
        int p1 = 0; int p2 =0;int dist = Integer.MAX_VALUE;
        while(p1<l1.size()&&p2<l2.size()){
            dist = Math.min(dist, Math.abs(l1.get(p1)-l2.get(p2)));
            if(l1.get(p1)<l2.get(p2) && p1<l1.size()) p1++;
            else if(l1.get(p1)>=l2.get(p2)&&p2<l2.size()) p2++;
        }

        while(p1<l1.size()){
            dist = Math.min(dist, Math.abs(l1.get(p1)-l2.get(p2-1)));
            p1++;
        }

        while(p2<l2.size()){
            dist = Math.min(dist, Math.abs(l1.get(p1-1)-l2.get(p2)));
            p2++;
        }

        return dist;
    }
}

Shortest Word Distance III

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

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

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

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

当两个word一样的时, word1idx = word2idx; word2idx=cur; dist = word2idx-word1idx;

public class Solution {
    public int shortestWordDistance(String[] words, String word1, String word2) {
        int p1 = -1; int p2 = -1; int min = Integer.MAX_VALUE; 
        for(int i=0;i<words.length;i++){
            if(words[i].equals(word1))
                p1 = i;
            if(words[i].equals(word2)){
                    if(word1.equals(word2))
                        p1 = p2;
                p2 = i;
            }

            if(p1!=-1 && p2!=-1){
                min = Math.min(min, Math.abs(p1-p2));
            }
        }
        return min;
    }
}

这道题还可以根据II data structure design再变种

shortestWordDistance类