[LeetCode] Word Shortest Distance II

Posted on 2020-03-29 Edited on 2020-04-12 In LeetCode Disqus:

Question:
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"].

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

1 2	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.

Analysis:

This one is an advanced question to the Word Shortest Distance quiz. In this question, you need to implement a function to provide the shortest distance back to the function caller. The implementation would be the same. All you need to think about is to check the boundary or edge cases of the word dictionary, e.g., null array, empty array.

Let’s see two different versions here:

Kotlin version

class WordDistance(
  private val words: Array<String>
) {

  fun shortest(word1: String, word2: String): Int {
    if (words.size == 0) return -1
    var wordIndex1 = -1
    var wordIndex2 = -1 
    var minDistance = Int.MAX_VALUE
    
    for ((index, word) in words.withIndex()) {
      if (word.equals(word1)) wordIndex1 = index 
      if (word.equals(word2)) wordIndex2 = index
      if (wordIndex1 != -1 && wordIndex2 != -1) {
        if (minDistance > Math.abs(wordIndex1 - wordIndex2)) {
          minDistance = Math.abs(wordIndex1 - wordIndex2)
        }
      }
    }
    return minDistance
  }
}

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

After you run this function, you can see the result:

1	Runtime: 1384 ms, faster than 17.65% of Kotlin online submissions for Shortest Word Distance II.

It seems too slow; let’s see how the Java version does.

Java version

class WordDistance {
  private String[] data; 

  public WordDistance(String[] words) {
    data = words;
  }

  public int shortest(String word1, String word2) {
    int wordIndex1 = -1, wordIndex2 = -1; 
    int minDistance = Integer.MAX_VALUE;
    
    if (data == null || data.length == 0) return minDistance;
    for (int i = 0; i < data.length; i++) {
      if (data[i].equals(word1)) wordIndex1 = i; 
      if (data[i].equals[word2]) wordIndex2 = i;
      
      if (wordIndex1 != -1 && wordIndex2 != -1) {
        if (minDistance > Math.abs(wordIndex1 - wordIndex2)) {
          minDistance = Math.abs(wordIndex1 - wordIndex2);
        }
      }
    }
    return minDistance;
  }
}

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

After you run the sample, you can see the result:

1	Time Limit Exceeded

It’s obvious when we deal with a sizable word dictionary (said more than 1 million words), this method couldn’t work at all. How can we improve this? Let’s involve some data structure into the code.

Kotlin version

class WordDistance(
  private val words: Array<String>
) {
  val map = mutableMapOf<String, Array<Int>>()

  init {
    words.forEachIndexed { index, word -> 
      val list: Array<Int> = map.getOrDefault(word, emptyArray())
      map[word] = list + index
    }
  }

  fun shortest(word1: String, word2: String): Int {
    val word1s = map[word1]!!
    val word2s = map[word2]!!
    var minDistance = Int.MAX_VALUE
    
    word1s.forEach { index1 -> 
      word2s.forEach {  index2 -> 
        if (minDistance > Math.abs(index1 - index2)) {
          minDistance = Math.abs(index1 - index2)
        }
      }
    }
    return minDistance
  }
}

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

Let’s see the result:

1 2	Runtime: 320 ms, faster than 23.53% of Kotlin online submissions for Shortest Word Distance II. Memory Usage: 44.1 MB, less than 100.00% of Kotlin online submissions for Shortest Word Distance II.

It’s much fast.

Java version

class WordDistance {
  private HashMap<String, ArrayList<Integer>> map = new HashMap();

  public WordDistance(String[] words) {    
    // initialize the map to maintain a list of indice for the word's position
    for (int i = 0; i < words.length; i++) {
      if (map.containsKey(words[i])) {
        ArrayList<Integer> list = map.get(words[i]);
        list.add(i);
        map.put(words[i], list);
      }
      else {
        ArrayList<Integer> list = new ArrayList();
        list.add(i);
        map.put(words[i], list);
      }
    }
  }

  public int shortest(String word1, String word2) {
    int minDistance = Integer.MAX_VALUE;
    ArrayList<Integer> word1s = map.get(word1); 
    ArrayList<Integer> word2s = map.get(word2);
    for (int index1 : word1s) {
      for (int index2 : word2s) {
        if (minDistance > Math.abs(index1 - index2)) {
          minDistance = Math.abs(index1 - index2);
        }
      }
    }

    return minDistance;
  }
}

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

After the improvement, you can see the result got much better:

1	Runtime: 24 ms, faster than 85.53% of Java online submissions for Shortest Word Distance II.

The runtime complexity would be O(n) because you still run through all elements to filter out the index of a specific word. The space complexity would be O(n) as well because you need to prepare a Map to store related information.

[LeetCode] Word Shortest Distance II

Posted on 2020-03-29 Edited on 2020-04-12 In LeetCode Disqus:

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

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

1 2	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.

Analysis:

Let’s see two different versions here:

Kotlin version

class WordDistance(
  private val words: Array<String>
) {

  fun shortest(word1: String, word2: String): Int {
    if (words.size == 0) return -1
    var wordIndex1 = -1
    var wordIndex2 = -1 
    var minDistance = Int.MAX_VALUE
    
    for ((index, word) in words.withIndex()) {
      if (word.equals(word1)) wordIndex1 = index 
      if (word.equals(word2)) wordIndex2 = index
      if (wordIndex1 != -1 && wordIndex2 != -1) {
        if (minDistance > Math.abs(wordIndex1 - wordIndex2)) {
          minDistance = Math.abs(wordIndex1 - wordIndex2)
        }
      }
    }
    return minDistance
  }
}

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

After you run this function, you can see the result:

1	Runtime: 1384 ms, faster than 17.65% of Kotlin online submissions for Shortest Word Distance II.

It seems too slow; let’s see how the Java version does.

Java version

class WordDistance {
  private String[] data; 

  public WordDistance(String[] words) {
    data = words;
  }

  public int shortest(String word1, String word2) {
    int wordIndex1 = -1, wordIndex2 = -1; 
    int minDistance = Integer.MAX_VALUE;
    
    if (data == null || data.length == 0) return minDistance;
    for (int i = 0; i < data.length; i++) {
      if (data[i].equals(word1)) wordIndex1 = i; 
      if (data[i].equals[word2]) wordIndex2 = i;
      
      if (wordIndex1 != -1 && wordIndex2 != -1) {
        if (minDistance > Math.abs(wordIndex1 - wordIndex2)) {
          minDistance = Math.abs(wordIndex1 - wordIndex2);
        }
      }
    }
    return minDistance;
  }
}

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

After you run the sample, you can see the result:

1	Time Limit Exceeded

Kotlin version

class WordDistance(
  private val words: Array<String>
) {
  val map = mutableMapOf<String, Array<Int>>()

  init {
    words.forEachIndexed { index, word -> 
      val list: Array<Int> = map.getOrDefault(word, emptyArray())
      map[word] = list + index
    }
  }

  fun shortest(word1: String, word2: String): Int {
    val word1s = map[word1]!!
    val word2s = map[word2]!!
    var minDistance = Int.MAX_VALUE
    
    word1s.forEach { index1 -> 
      word2s.forEach {  index2 -> 
        if (minDistance > Math.abs(index1 - index2)) {
          minDistance = Math.abs(index1 - index2)
        }
      }
    }
    return minDistance
  }
}

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

Let’s see the result:

1 2	Runtime: 320 ms, faster than 23.53% of Kotlin online submissions for Shortest Word Distance II. Memory Usage: 44.1 MB, less than 100.00% of Kotlin online submissions for Shortest Word Distance II.

It’s much fast.

Java version

class WordDistance {
  private HashMap<String, ArrayList<Integer>> map = new HashMap();

  public WordDistance(String[] words) {    
    // initialize the map to maintain a list of indice for the word's position
    for (int i = 0; i < words.length; i++) {
      if (map.containsKey(words[i])) {
        ArrayList<Integer> list = map.get(words[i]);
        list.add(i);
        map.put(words[i], list);
      }
      else {
        ArrayList<Integer> list = new ArrayList();
        list.add(i);
        map.put(words[i], list);
      }
    }
  }

  public int shortest(String word1, String word2) {
    int minDistance = Integer.MAX_VALUE;
    ArrayList<Integer> word1s = map.get(word1); 
    ArrayList<Integer> word2s = map.get(word2);
    for (int index1 : word1s) {
      for (int index2 : word2s) {
        if (minDistance > Math.abs(index1 - index2)) {
          minDistance = Math.abs(index1 - index2);
        }
      }
    }

    return minDistance;
  }
}

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

After the improvement, you can see the result got much better:

1	Runtime: 24 ms, faster than 85.53% of Java online submissions for Shortest Word Distance II.