Leetcode - 243~245. 最短单词距离

class Solution {

    /**
     * 已知条件：字符串数组words，字符串word1和word2，两个字符串不相等并且都在数组中
     * 题目要求：找到这两个字符串在数组中的最短距离（也就是最小的下标差值）
     * 举例说明：words = ["1", "2", "3", "3", "1"], word1 = "1", word2 = "3"; shortestDistance = 1
     */
    
    public int shortestDistance1(String[] words, String word1, String word2) {

        //idx1/idx2用于保存最近找到的word1/word2的下标
        int idx1 = -1, idx2 = -1, min = Integer.MAX_VALUE;
        
        //遍历数组，如果找到了word1/word2，则更新idx1/idx2的值，并更新word1和word2的最短距离
        for(int i = 0; i < words.length; i++){
            if(words[i].equals(word1)){
                idx1 = i;
                if(idx2 != -1)
                    min = Math.min(min, idx1 - idx2);
            
            }else if(words[i].equals(word2)){
                idx2 = i;
                if(idx1 != -1)
                    min = Math.min(min, idx2 - idx1);
            }
        }
        return min;
    }


    /**
     * 进阶（题目二）：字符串数组在创建本类对象时就已经给出了，并且需要多次计算两个不同字符串的最短距离
     */
    
    //这种情况下，可以先将字符串和它对应的下标存储到Map中
    private Map<String, List<Integer>> map;
    public Solution(String[] words){ initMap(words); }
    private void initMap(String[] words){
        map = new HashMap<>();
        for(int i = 0; i < words.length; i++){
            List<Integer> idxs = map.get(words[i]);
            if(idxs == null){
                idxs = new ArrayList<>();
                map.put(words[i], idxs);
            }
            idxs.add(i);
        }
    }
    
    public int shortestDistance2(String word1, String word2) {

        //获取到word1/word2的所有下标
        List<Integer> idxs1 = map.get(word1), idxs2 = map.get(word2);
        
        //i1/i2用于遍历idxs1/idxs2数组
        int i1 = 0, i2 = 0, min = Integer.MAX_VALUE;
        
        while(i1 < idxs1.size() && i2 < idxs2.size()){
            
            //获取到第i1个word1和第i2个word2所在的下标，并更新最短距离
            int idx1 = idxs1.get(i1), idx2 = idxs2.get(i2);
            min = Math.min(min, Math.abs(idx1 - idx2));
            
            //如果第i1个word1在第i2个word2左边，则下次应该让第(i1 + 1)个word1和第i2个word2来比较；反过来也同理
            int tem = idx1 < idx2 ? i1++ : i2++;
        }
        
        return min;
    }


    /**
     * 进阶（题目三）：两个字符串可能相等，但此时它们在数组中的下标不同（也就是说此时不能返回0）
     */

    public int shortestDistance3(String[] words, String word1, String word2) {

        //如果两个字符串不相等，则直接用第一种方法进行判断即可
        if(!word1.equals(word2))
            return shortestDistance1(words, word1, word2);
        
        //pre表示前一个word1所在的下标
        int pre = -1, min = Integer.MAX_VALUE;
        
        for(int i = 0; i < words.length; i++){
            if(words[i].equals(word1)){
                if(pre != -1)
                    min = Math.min(min, i - pre);
                pre = i;
            }
        }
        return min;
    }
}