LeetCode 243 Shortest Word Distance I (Easy)

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

Example:

Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Input: word1 = “coding”, word2 = “practice”
Output: 3
Input: word1 = "makes", word2 = "coding"
Output: 1

Note:

• You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

class Solution {
    public int shortestDistance(String[] words, String word1, String word2) {
        if (words == null || words.length == 0 || word1 == null || word1.length () == 0 || word2 == null || word2.length () == 0)
            return 0;
        
        List<Integer> word2IndexList = new ArrayList<> ();
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals (word2)) {
                word2IndexList.add (i);
            }
        }
        
        int shortest = Integer.MAX_VALUE;
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals (word1)) {
                
                for (int index : word2IndexList) {
                    shortest = Math.min (shortest, Math.abs (index - i));
                }
            }
        }
        
        return shortest;
    }
}

LeetCode 244 Shortest Word Distance II (Medium)

Design a class which receives a list of words in the constructor, and implements a method that takes two words word1 and word2 and return the shortest distance between these two words in the list. Your method will be called repeatedly many times with different parameters.

Example:

Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Input: word1 = “coding”, word2 = “practice”
Output: 3
Input: word1 = "makes", word2 = "coding"
Output: 1

Note:

• You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

Solution: HashMap + Two Pointers

class WordDistance {
    Map<String, List<Integer>> wordVsIndex;
    
    public WordDistance(String[] words) {
        this.wordVsIndex = new HashMap<String, List<Integer>> ();
        
        for (int i = 0; i < words.length; i++) {
            List<Integer> list = this.wordVsIndex.getOrDefault (words[i], new ArrayList<Integer> ());
            list.add (i);
            this.wordVsIndex.put (words[i], list);
        }
    }
    
    public int shortest(String word1, String word2) {
        List<Integer> word1List = this.wordVsIndex.get (word1);
        List<Integer> word2List = this.wordVsIndex.get (word2);
        
        int shortest = Integer.MAX_VALUE;
        
        // for (int word1Index : word1List) {
        //     for (int word2Index : word2List) {
        //         shortest = Math.min (shortest, Math.abs (word2Index - word1Index));
        //     }
        // }
        
        int start1 = 0;
        int start2 = 0;
        
        while (start1 < word1List.size () && start2 < word2List.size ()) {
            int index1 = word1List.get (start1);
            int index2 = word2List.get (start2);
            
            if (index1 > index2) {
                start2 ++;
            } else {
                start1 ++;
            }
            
            shortest = Math.min (shortest, Math.abs (index2 - index1));
        }
        
        return shortest;
    }
}

/**
 * Your WordDistance object will be instantiated and called as such:
 * WordDistance obj = new WordDistance(words);
 * int param_1 = obj.shortest(word1,word2);
 */

LeetCode 245 Shortest Word Distance III (Medium)

• Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
• word1 and word2 may be the same and they represent two individual words in the list.

Example:

Assume that words = ["practice", "makes", "perfect", "coding", "makes"].

Input: word1 = “makes”, word2 = “coding”
Output: 1
Input: word1 = "makes", word2 = "makes"
Output: 3

Note:

• You may assume word1 and word2 are both in the list.

Solution

1. Solution1: HashMap + 分别处理word1和Word2相等，和不相等的两种情况
2. Solution2 (faster)：直接遍历数组，每次取到word1或者word2的index的时候，就计算两者之间的距离。

class Solution {
    public int shortestWordDistance(String[] words, String word1, String word2) {
        if (words == null || words.length == 0 || word1 == null || word1.length () == 0 || word2 == null || word2.length () == 0)
            return 0;
        
        /*
        Map<String, List<Integer>> wordVsIndex = new HashMap<> ();
        for (int i = 0; i < words.length; i ++) {
            List<Integer> list = wordVsIndex.getOrDefault (words[i], new ArrayList<> ());
            list.add (i);
            wordVsIndex.put (words[i], list);
        }
        
        int shortest = Integer.MAX_VALUE;
        if (word1.equals (word2)) {
            List<Integer> list = wordVsIndex.get (word1);
            if (list.size () <= 1)
                return 0;
            
            
            int prev = list.get (0);
            for (int i = 1; i < list.size (); i++) {
                int currentIndex = list.get (i);
                shortest = Math.min (shortest, Math.abs (currentIndex - prev));
                prev = currentIndex;
            }
            
            return shortest;
        }
        
        int start1 = 0;
        int start2 = 0;
        
        List<Integer> word1Index = wordVsIndex.get (word1);
        List<Integer> word2Index = wordVsIndex.get (word2);
        
        while (start1 < word1Index.size () && start2 < word2Index.size ()) {
            int index1 = word1Index.get (start1);
            int index2 = word2Index.get (start2);
            
            if (index1 > index2) {
                start2 ++;
            } else {
                start1 ++;
            }
            
            shortest = Math.min (shortest, Math.abs (index2 - index1));
        }
        
        return shortest;
        */
        int shortest = Integer.MAX_VALUE;
        
        if (word1.equals (word2)) {
            int prev = -1;
            
            for (int i = 0; i < words.length; i++) {
                if (prev != -1 && words[i].equals (word1)) {
                    shortest = Math.min (shortest, Math.abs (i - prev));
                    prev = i;
                } else if (words[i].equals (word1)) {
                    prev = i;
                }
            }
            
            return shortest;
        }
        
        int start1 = -1;
        int start2 = -1;
        
        for (int i = 0; i < words.length; i++) {
            if (words[i].equals (word1)) {
                start1 = i;
            } else if (words[i].equals (word2)) {
                start2 = i;
            }
            
            if (start1 != -1 && start2 != -1) {
                shortest = Math.min (shortest, Math.abs (start1 - start2));
            }
        }
        
        return shortest;
    }
}