Array
String
Description
Given an array of strings wordsDict
and two strings that already exist in the array word1
and word2
, return the shortest distance between the occurrence of these two words in the list .
Note that word1
and word2
may be the same. It is guaranteed that they represent two individual words in the list.
Example 1:
Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1
Example 2:
Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "makes"
Output: 3
Constraints:
1 <= wordsDict.length <= 105
1 <= wordsDict[i].length <= 10
wordsDict[i]
consists of lowercase English letters.
word1
and word2
are in wordsDict
.
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution :
def shortestWordDistance ( self , wordsDict : List [ str ], word1 : str , word2 : str ) -> int :
ans = len ( wordsDict )
if word1 == word2 :
j = - 1
for i , w in enumerate ( wordsDict ):
if w == word1 :
if j != - 1 :
ans = min ( ans , i - j )
j = i
else :
i = j = - 1
for k , w in enumerate ( wordsDict ):
if w == word1 :
i = k
if w == word2 :
j = k
if i != - 1 and j != - 1 :
ans = min ( ans , abs ( i - j ))
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 class Solution {
public int shortestWordDistance ( String [] wordsDict , String word1 , String word2 ) {
int ans = wordsDict . length ;
if ( word1 . equals ( word2 )) {
for ( int i = 0 , j = - 1 ; i < wordsDict . length ; ++ i ) {
if ( wordsDict [ i ] . equals ( word1 )) {
if ( j != - 1 ) {
ans = Math . min ( ans , i - j );
}
j = i ;
}
}
} else {
for ( int k = 0 , i = - 1 , j = - 1 ; k < wordsDict . length ; ++ k ) {
if ( wordsDict [ k ] . equals ( word1 )) {
i = k ;
}
if ( wordsDict [ k ] . equals ( word2 )) {
j = k ;
}
if ( i != - 1 && j != - 1 ) {
ans = Math . min ( ans , Math . abs ( i - j ));
}
}
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 class Solution {
public :
int shortestWordDistance ( vector < string >& wordsDict , string word1 , string word2 ) {
int n = wordsDict . size ();
int ans = n ;
if ( word1 == word2 ) {
for ( int i = 0 , j = -1 ; i < n ; ++ i ) {
if ( wordsDict [ i ] == word1 ) {
if ( j != -1 ) {
ans = min ( ans , i - j );
}
j = i ;
}
}
} else {
for ( int k = 0 , i = -1 , j = -1 ; k < n ; ++ k ) {
if ( wordsDict [ k ] == word1 ) {
i = k ;
}
if ( wordsDict [ k ] == word2 ) {
j = k ;
}
if ( i != -1 && j != -1 ) {
ans = min ( ans , abs ( i - j ));
}
}
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 func shortestWordDistance ( wordsDict [] string , word1 string , word2 string ) int {
ans := len ( wordsDict )
if word1 == word2 {
j := - 1
for i , w := range wordsDict {
if w == word1 {
if j != - 1 {
ans = min ( ans , i - j )
}
j = i
}
}
} else {
i , j := - 1 , - 1
for k , w := range wordsDict {
if w == word1 {
i = k
}
if w == word2 {
j = k
}
if i != - 1 && j != - 1 {
ans = min ( ans , abs ( i - j ))
}
}
}
return ans
}
func abs ( x int ) int {
if x < 0 {
return - x
}
return x
}
GitHub