Monday, August 24, 2015

Leetcode: Shortest Word Distance

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.
For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Given word1 = “coding”word2 = “practice”, return 3.
Given word1 = "makes"word2 = "coding", return 1.
Note:
You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.
Understand the problem:
The problem can be solved by one-pass of the array. 
Iterate through the array, use two pointers pointing to the index of the word1 and word2, maintain the minimum distance. 

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

2 comments:

  1. Instead of this block:
    if (posA != -1 && posB != -1) {
    minDistance = Math.min(minDistance, Math.abs(posA - posB));
    }

    Efficient one is (we donot need to comapre for every word after first occurence):
    if (posA != -1 && posB != -1) {
    minDistance = Math.min(minDistance, Math.abs(posA - posB));
    if(posA >posB)
    posB =-1;
    else
    posA=-1;
    }

    ReplyDelete
  2. I am impressed. I don't think Ive met anyone who knows as much about this subject as you do. You are truly well informed and very intelligent. You wrote something that people could understand and made the subject intriguing for everyone. Really, great blog you have got here. what is the shortest word in english

    ReplyDelete