Copy **Input:** wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
**Output:** 1
Copy **Input:** wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "makes"
**Output:** 3
this one is stupid, why you need to have a map? a waste time and space.
Copy class Solution {
public int shortestWordDistance ( String [] words , String word1 , String word2) {
// edge cases
if ( words . length < 2 ) return 0 ;
Map < String , List < Integer >> map = new HashMap < String , List < Integer >>();
// walk array, get map
for ( int i = 0 ; i < words . length ; i ++ ) {
if ( map . containsKey (words[i])) {
map . get (words[i]) . add (i);
} else {
List < Integer > tmp = new ArrayList < Integer >();
tmp . add (i);
map . put (words[i] , tmp);
}
}
return minDiff( map . get(word1) , map . get(word2)) ;
}
private int minDiff ( List < Integer > l1 , List < Integer > l2) {
int diff = Integer . MAX_VALUE ;
// same list, same word
if (l1 == l2) {
for ( int i = 1 ; i < l1 . size (); i ++ ) {
diff = Math . min (diff ,
Math . abs ( l1 . get (i) - l1 . get (i - 1 )));
}
return diff;
}
// binary search longer one
List < Integer > s = l1 , l = l2;
if ( l1 . size () > l2 . size ()) {
l = l1; s = l2;
}
for ( int i = 0 ; i < s . size (); i ++ ) {
int target = s . get (i);
int left = 0 , right = l . size () - 1 ;
while (left + 1 < right) {
int mid = left + (right - left) / 2 ;
if ( l . get (mid) > target) right = mid;
else left = mid;
}
diff = Math . min (diff ,
Math . min ( Math . abs ( l . get (left) - target) , Math . abs ( l . get (right) - target)));
}
return diff;
}
}
Copy class Solution {
public int shortestWordDistance ( String [] words , String word1 , String word2) {
// edge cases
if ( words . length < 2 ) return 0 ;
int prev = - 1 ;
int diff = Integer . MAX_VALUE ;
for ( int i = 0 ; i < words . length ; i ++ ) {
if (words[i] . equals (word1) || words[i] . equals (word2)) {
if (prev != - 1 ) {
if ( word1 . equals (word2)) {
diff = Math . min (diff , i - prev);
} else if ( ! words[i] . equals (words[prev])) {
diff = Math . min (diff , i - prev);
}
}
prev = i;
}
}
return diff;
}
}
Copy // intuition: 1) time complexity can be optimized? 2) space can be optimized?
class Solution {
public int shortestWordDistance ( String [] words , String word1 , String word2) {
// edge cases
if ( words . length < 2 ) return 0 ;
int i1 = - 1 , i2 = - 1 ;
int diff = Integer . MAX_VALUE ;
for ( int i = 0 ; i < words . length ; i ++ ) {
if (words[i] . equals (word1)) {
if ( word1 . equals (word2)) {
i2 = i1;
i1 = i;
} else {
i1 = i;
}
} else if (words[i] . equals (word2)) {
i2 = i;
}
if (i1 >= 0 && i2 >= 0 ) diff = Math . min (diff ,
Math . abs (i1 - i2));
}
return diff;
}
}