Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/245.html
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
andword2
are inwordsDict
.
Algorithm
A condition is added here, that is, two words may be the same.
When word1
and word2
are equal, use p1
to save the result of p2
, and p2
is assigned to the current position i
, so that the result can be updated.
If word1
and word2
are not equal, the same logic is still valid.
Code
-
public class Shortest_Word_Distance_III { public static void main(String[] args) { Shortest_Word_Distance_III out = new Shortest_Word_Distance_III(); Solution s = out.new Solution(); // output: 2 System.out.println( s.shortestWordDistance(new String[]{"makes", "practice", "makes", "perfect", "coding", "makes"}, "makes", "makes")); } 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; // this is covering normal cases, word1 not same as word2 } if (posA != -1 && posB != -1 && posA != posB) { // @note: update before reset posB minDistance = Math.min(minDistance, Math.abs(posA - posB)); } if (word1.equals(word2)) { // always updating posA in above line, so after checking update posB // so that, posB is always the most recent word's index posB = posA; } } return minDistance; } } } ############ 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; } }
-
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; } };
-
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: # i != -1 too, so both words found 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 class Solution: # combine above if-else def shortestWordDistance(self, words: List[str], word1: str, word2: str) -> int: posA = -1 posB = -1 minDistance = float("inf") for i in range(len(words)): word = words[i] if word == word1: posA = i elif word == word2: posB = i if posA != -1 and posB != -1 and posA != posB: minDistance = min(minDistance, abs(posA - posB)) if word1 == word2: posB = posA return minDistance ############ class Solution(object): def shortestWordDistance(self, words, word1, word2): """ :type words: List[str] :type word1: str :type word2: str :rtype: int """ ans = float("inf") idx1 = idx2 = -1 for i in range(0, len(words)): word = words[i] if word in (word1, word2): if word == word1: idx1 = i if idx2 != -1 and idx1 != idx2: ans = min(ans, abs(idx2 - idx1)) if word == word2: idx2 = i if idx1 != -1 and idx1 != idx2: ans = min(ans, abs(idx2 - idx1)) return ans
-
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 min(a, b int) int { if a < b { return a } return b } func abs(x int) int { if x < 0 { return -x } return x }