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 =

Assume that words =

`["practice", "makes", "perfect", "coding", "makes"]`

.
Given

Given

*word1*=`“makes”`

, *word2*=`“coding”`

, return 1.Given

*word1*=`"makes"`

, *word2*=`"makes"`

, return 3.
Note:

You may assume

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; } }

This comment has been removed by the author.

ReplyDeleteThis comment has been removed by the author.

ReplyDelete// get indexes of word1 say 1 15 26 39

ReplyDelete// 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;

}