Monday, August 24, 2015

Leetcode: Shortest Word Distance III

This is a follow up of Shortest Word Distance. The only difference is now word1 could be the same as word2.
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.
For example,
Assume that words = ["practice", "makes", "perfect", "coding", "makes"].
Given word1 = “makes”word2 = “coding”, return 1.
Given word1 = "makes"word2 = "makes", return 3.
Note:
You may assume word1 and word2 are both in the list.Understand the problem:
Understand the problem:
The problem is an extension of the previous one. The only diff is the word1 and word2 can be the same. It can still be easily solved by using a hash map. The question is, can we solve it by using the one-pass of the array? 

The key is we cannot update the two pointers simultaneously, if they are the same. We could update one, compare the distance, and then update the other. 

Code (Java):
public class Solution {
    public int shortestWordDistance(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++) {
            String word = words[i];
            
            if (word.equals(word1)) {
                posA = i;
            } else if (word.equals(word2)) {
                posB = i;
            }
            
            if (posA != -1 && posB != -1 && posA != posB) {
                minDistance = Math.min(minDistance, Math.abs(posA - posB));
            }
            
            if (word1.equals(word2)) {
                posB = posA;
            }
        }
        
        return minDistance;
    }
}

4 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. This comment has been removed by the author.

    ReplyDelete
  3. // get indexes of word1 say 1 15 26 39
    // get indexes of word2 say 14 25 28 48

    The above code returns 3 but should return 1;

    for loop should have code something like this...

    For loop:{
    if(i>1){
    currentDist = Math.abs(word1.get(i-1) - word2.get(i));
    if(currentDist < smallest_distance_so_far)
    smallest_distance_so_far = currentDist;

    currentDist = Math.abs(word1.get(i) - word2.get(i-1));
    if(currentDist < smallest_distance_so_far)
    smallest_distance_so_far = currentDist;
    }

    currentDist = Math.abs(word1.get(i) - word2.get(i));
    if(currentDist < smallest_distance_so_far)
    smallest_distance_so_far = currentDist;

    }

    ReplyDelete
  4. Very efficiently written information. It will be beneficial to anybody who utilizes it, including me. Keep up the good work. For sure i will check out more posts. This site seems to get a good amount of visitors. shortest word in english

    ReplyDelete