LeetCode 245: Shortest Word Distance III

Problem Restatement

We are given a list of words called wordsDict and two words, word1 and word2.

We need to return the shortest distance between the two words in the list.

The distance between two words is the absolute difference between their indices.

Unlike the previous problem, word1 and word2 may be the same word.

If they are the same, we must use two different occurrences.

Input and Output

Example function shape:

def shortestWordDistance(wordsDict: list[str], word1: str, word2: str) -> int:
    ...

Examples

Example 1:

wordsDict = ["practice", "makes", "perfect", "coding", "makes"]
word1 = "makes"
word2 = "coding"

"makes" appears at indices 1 and 4.

"coding" appears at index 3.

The closest distance is:

abs(4 - 3) = 1

So the answer is:

1

Example 2:

wordsDict = ["practice", "makes", "perfect", "coding", "makes"]
word1 = "makes"
word2 = "makes"

Now both target words are the same.

We must use two different occurrences.

The word "makes" appears at indices:

1 and 4

The distance is:

abs(4 - 1) = 3

So the answer is:

3

First Thought

For different words, we can reuse the solution from LeetCode 243.

We scan from left to right and store the latest index of each word.

But when:

word1 == word2

the previous logic breaks.

We cannot store only one index and compare it with itself.

Instead, we must compare consecutive occurrences of the same word.

Key Insight

There are two cases.

Case 1: Different Words

If:

word1 != word2

we use the normal approach:

last1 = latest index of word1
last2 = latest index of word2

Every time both indices exist, update the answer.

Case 2: Same Word

If:

word1 == word2

then we only care about the distance between consecutive occurrences.

For example:

["a", "x", "a", "x", "a"]

The shortest distance must come from neighboring "a" positions.

So we track:

previous occurrence of the word

Whenever we see the word again, compute the distance to the previous occurrence.

Algorithm

Different Words

1. Initialize:

last1 = -1
last2 = -1
answer = infinity

2. Scan the array.
3. Update the latest index for each word.
4. Whenever both indices exist, update the minimum distance.

Same Word

1. Initialize:

previous = -1
answer = infinity

2. Scan the array.
3. When the word appears:
   • If previous exists, compute the distance.
   • Update previous.

Correctness

Different Words

At every step, last1 and last2 store the latest occurrences of word1 and word2.

When a new occurrence appears, the closest possible partner among earlier positions is the latest occurrence of the other word. Any older occurrence is farther away.

Thus, every potentially optimal pair is checked.

Same Word

Suppose the target word appears at indices:

i1 < i2 < i3 < ...

The shortest distance must occur between two consecutive occurrences.

Why?

For any non-consecutive pair:

ik and ij where j > k + 1

there exists another occurrence between them, so:

ij - ik

is larger than at least one consecutive distance.

Therefore, checking consecutive occurrences is sufficient.

Complexity

Implementation

class Solution:
    def shortestWordDistance(
        self,
        wordsDict: list[str],
        word1: str,
        word2: str,
    ) -> int:

        answer = float("inf")

        if word1 == word2:
            previous = -1

            for i, word in enumerate(wordsDict):
                if word == word1:
                    if previous != -1:
                        answer = min(answer, i - previous)

                    previous = i

        else:
            last1 = -1
            last2 = -1

            for i, word in enumerate(wordsDict):
                if word == word1:
                    last1 = i

                elif word == word2:
                    last2 = i

                if last1 != -1 and last2 != -1:
                    answer = min(answer, abs(last1 - last2))

        return answer

Code Explanation

We start with:

answer = float("inf")

This stores the best distance found so far.

Then we split into two cases.

Same Word Case

if word1 == word2:

We store the previous occurrence:

previous = -1

Whenever we see the word again:

if previous != -1:
    answer = min(answer, i - previous)

Then we update:

previous = i

Different Word Case

We store the latest index of each word:

last1 = -1
last2 = -1

When either word appears, update its latest index.

If both exist, compute:

abs(last1 - last2)

and update the answer.

Testing

def run_tests():
    s = Solution()

    assert s.shortestWordDistance(
        ["practice", "makes", "perfect", "coding", "makes"],
        "makes",
        "coding",
    ) == 1

    assert s.shortestWordDistance(
        ["practice", "makes", "perfect", "coding", "makes"],
        "makes",
        "makes",
    ) == 3

    assert s.shortestWordDistance(
        ["a", "b", "a"],
        "a",
        "a",
    ) == 2

    assert s.shortestWordDistance(
        ["a", "x", "b", "a", "b"],
        "a",
        "b",
    ) == 1

    assert s.shortestWordDistance(
        ["x", "a", "x", "a", "x", "a"],
        "a",
        "a",
    ) == 2

    print("all tests passed")

run_tests()