243,244,245. Shortest Word Distance

https://leetcode.com/problems/shortest-word-distance/description/

image.png

这道题就用到贪心思想。为什么我们从前往后遍历，如果2个要比较的STRING都齐备了。那么一旦一个更新了，就看看距离有没有更新就好了。

public int shortestDistance(String[] all, String s, String e) {
        int p1 = -1,p2=-1;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < all.length; i++){
            String cur = all[i];
            if(cur.equals(s)){
                p1 = i;
                if(p2 != -1){
                    min = Math.min(min,p1-p2);
                }
            }else if(cur.equals(e)){
                p2 = i;
                if(p1 != -1){
                    min = Math.min(min,p2-p1);
                }
            }
        }
        return min;
    }

follow up : 如果会调用多次。那么就用HASHMAP 把每个STRING出现的次数存下来。

Map<String,List<Integer>> map = new HashMap<>();
    public WordDistance(String[] words) {
        int idx = 0;
        for(String w : words){
            map.putIfAbsent(w,new ArrayList<>());
            map.get(w).add(idx++);
        }
    }
    
    public int shortest(String word1, String word2) {
        List<Integer> a = map.get(word1);
        List<Integer> b = map.get(word2);
        int i = 0, j = 0;
        int min = Integer.MAX_VALUE;
        while(i < a.size() && j < b.size()){
            int p1 = a.get(i);
            int p2 = b.get(j);
            if(p1<p2){
                i++;
            }else{
                j++;
            }
            min = Math.min(min,Math.abs(p1-p2));
        }
        return min;
    }

follow up : 如果允许重复的单词
那么就重复的单词，单独写一个逻辑。
第一个记录好后，第二个来了就更新MIN，随后把第一个赋值给第二个，继续等下一个‘’第二个‘’

public int shortestWordDistance(String[] all, String s1, String s2) {
        int p1 = -1, p2 = -1;
        int min = Integer.MAX_VALUE;
        if(s1.equals(s2)){
            for(int i = 0; i < all.length; i++){
                String cur = all[i];
                if(!cur.equals(s1)) continue;
                if(p1 == -1){
                    p1 = i;
                }else if(p2 == -1){
                    p2 = i;
                    min = Math.min(min, p2-p1);
                    p1 = p2;
                    p2 = -1;
                }
            }
        }else{
            for(int i = 0; i < all.length; i++){
                String cur = all[i];
                if(s1.equals(cur)){
                    p1 = i;
                    if(p2 != -1)
                        min = Math.min(min, p1-p2);
                }else if(s2.equals(cur)){
                    p2 = i;
                    if(p1 != -1)
                        min = Math.min(min, p2-p1);
                }
            }
        }
        return min;
    }