Skip to content

17.11. Find Closest

Description

You have a large text file containing words. Given any two words, find the shortest distance (in terms of number of words) between them in the file. If the operation will be repeated many times for the same file (but different pairs of words), can you optimize your solution?

Example: 


Input: words = ["I","am","a","student","from","a","university","in","a","city"], word1 = "a", word2 = "student"

Output: 1

Note:

  • words.length <= 100000

Solutions

Solution 1: Single Pass

We use two pointers $i$ and $j$ to record the most recent occurrences of the two words $\textit{word1}$ and $\textit{word2}$, respectively. Initially, $i = \infty$ and $j = -\infty$.

Next, we traverse the entire text file. For each word $w$, if $w$ equals $\textit{word1}$, we update $i = k$, where $k$ is the index of the current word; if $w$ equals $\textit{word2}$, we update $j = k$. Then we update the answer $ans = \min(ans, |i - j|)$.

After the traversal, we return the answer $ans$.

The time complexity is $O(n)$, where $n$ is the number of words in the text file. The space complexity is $O(1)$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def findClosest(self, words: List[str], word1: str, word2: str) -> int:
        i, j = inf, -inf
        ans = inf
        for k, w in enumerate(