LeetCode 245: Shortest Word Distance III Solution in Python – A Step-by-Step Guide

What Is LeetCode 245: Shortest Word Distance III?

In LeetCode 245: Shortest Word Distance III, you’re given a list of words (wordsDict) and two target words (word1 and word2), and your task is to find the minimum distance between any two occurrences of these words in the list. Unlike LeetCode 243: Shortest Word Distance, where the words must be distinct, here word1 and word2 can be the same, requiring us to consider distances between different instances of the same word.

Problem Statement

• Input: A list of strings wordsDict and two strings word1 and word2.
• Output: An integer representing the minimum distance between any occurrences of word1 and word2.
• Rules: Distance is the absolute difference between indices; if word1 == word2, find the minimum distance between distinct occurrences.

Constraints

• List length: 2 to 10^4.
• Word length: 1 to 10 characters.
• All words are lowercase; word1 and word2 are present in the list.

Examples

• Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
• Output: 1 (distance between "makes" at index 1 and "coding" at index 3).
• Input: Same list, word1 = "makes", word2 = "makes"
• Output: 3 (distance between "makes" at index 1 and index 4).
• Input: wordsDict = ["a", "a"], word1 = "a", word2 = "a"
• Output: 1.

Understanding the Problem: Flexible Word Gaps

To solve LeetCode 245: Shortest Word Distance III in Python, we need to find the smallest distance between any two positions of word1 and word2 in the list, even if they’re the same word. A naive approach—checking every pair of positions—works but is inefficient. Instead, we’ll use two methods: 1. Best Solution (Two-Pointer): O(n) time, O(1) space—fast and smart. 2. Alternative Solution (Brute Force): O(n²) time, O(n) space—simple but slower.

Let’s dive into the best solution with extra detail for beginners.

Best Solution: Two-Pointer Approach

Why This Is the Best Solution

The two-pointer approach is the top choice for LeetCode 245 because it scans the list just once, tracking the most recent positions of word1 and word2, and updates the minimum distance efficiently. It handles both cases—distinct words and identical words—in O(n) time with O(1) space, making it perfect for this problem.

How It Works (Super Detailed for Beginners)

Imagine you’re walking through the list with two markers: one for the last place you saw word1 and one for the last place you saw word2. Every time you find one of your words, you update its marker. If you’ve seen both words, you measure the distance between the markers and keep track of the smallest gap. The trick here is handling when word1 and word2 are the same—each new occurrence becomes the “second” marker, and the previous one becomes the “first.” Let’s break it down so it’s crystal clear:

• Set Up: Use two variables, pos1 and pos2, to store the latest positions of word1 and word2. Start them at -1 (meaning “not found yet”). Also, set a min_distance variable to a huge number (like infinity) to track the smallest gap.
• Walk the List: Go through each word in the list, one by one, using its index (position).
• Case 1: Words Are Different (word1 != word2):
• If the current word is word1, set pos1 to its index.
• If it’s word2, set pos2 to its index.
• If both pos1 and pos2 are set (not -1), calculate abs(pos1 - pos2) and update min_distance if it’s smaller.
• Case 2: Words Are the Same (word1 == word2):
• Each time you find the word, it’s a new occurrence.
• Move the previous position (pos1) to pos2 (like shifting the “last seen” to “second-to-last seen”).
• Set pos1 to the current index (the newest spot).
• If pos2 isn’t -1 (you’ve seen the word before), calculate abs(pos1 - pos2) and update min_distance.
• Finish: After the loop, min_distance has your answer.

Think of it like tracking two friends in a parade: if they’re different people, you note their latest spots; if they’re the same person, you track their last two appearances. Easy once you see it in action!

Step-by-Step Example

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

• Setup: pos1 = -1 (for "makes"), pos2 = -1 (for "coding"), min_distance = infinity.
• Index 0: "practice"—no match.
• Index 1: "makes"
• pos1 = 1, pos2 = -1.
• Index 2: "perfect"—no match.
• Index 3: "coding"
• pos2 = 3, pos1 = 1.
• Distance: abs(1 - 3) = 2, min_distance = 2.
• Index 4: "makes"
• pos1 = 4, pos2 = 3.
• Distance: abs(4 - 3) = 1, min_distance = 1.
• Result: 1.

Example 2: Same list, word1 = "makes", word2 = "makes"

• Setup: pos1 = -1, pos2 = -1, min_distance = infinity.
• Index 0: "practice"—no match.
• Index 1: "makes"
• First occurrence: pos1 = 1, pos2 = -1.
• Index 2: "perfect"—no match.
• Index 3: "coding"—no match.
• Index 4: "makes"
• Second occurrence: pos2 = 1 (old pos1), pos1 = 4 (new spot).
• Distance: abs(4 - 1) = 3, min_distance = 3.
• Result: 3.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass Solution:
    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
        # Step 1: Set up our tracking tools
        pos1 = -1  # Last position of word1 (or latest if same word)
        pos2 = -1  # Last position of word2 (or previous if same word)
        min_distance = float('inf')  # Start with a huge number

        # Step 2: Check if words are the same
        same_word = word1 == word2

        # Step 3: Walk through the list
        for i in range(len(wordsDict)):
            current_word = wordsDict[i]

            # Step 4: Handle the word we found
            if current_word == word1:
                if same_word:
                    # If same word, shift positions
                    pos2 = pos1  # Old position becomes "previous"
                    pos1 = i     # New position
                else:
                    pos1 = i  # Update word1’s position

            # Step 5: If words are different, check word2
            elif not same_word and current_word == word2:
                pos2 = i  # Update word2’s position

            # Step 6: Calculate distance if we have both
            if pos1 != -1 and pos2 != -1:
                distance = abs(pos1 - pos2)  # Measure the gap
                min_distance = min(min_distance, distance)  # Keep smallest

        # Step 7: Return the answer
        return min_distance

• Time Complexity: O(n)—one pass through the list.
• Space Complexity: O(1)—just two variables.

This solution is like a game of tag where you only need to remember the last two spots—it’s quick and simple once you get it!

Alternative Solution: Brute Force with Position Lists

Why an Alternative Approach?

The brute force approach is like making a list of every place you’ve seen each word and then checking all possible pairs. It’s slower but easier to follow for beginners, showing every step clearly before jumping to the optimized method.

How It Works

• Collect all positions of word1 and word2 in separate lists.
• If word1 == word2, use one list but compare different indices.
• Calculate the distance between all pairs and find the minimum.

Step-by-Step Example

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

• Positions: "makes": [1, 4]
• Pairs: (1, 4) → abs(1 - 4) = 3
• Output: 3.

Example: Same list, word1 = "makes", word2 = "coding"

• Positions: "makes": [1, 4], "coding": [3]
• Pairs: (1, 3) → 2, (4, 3) → 1
• Output: 1.

Code for Brute Force Approach

Copy codeclass Solution:
    def shortestWordDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
        # Step 1: Collect positions
        pos1 = []
        pos2 = []
        for i, word in enumerate(wordsDict):
            if word == word1:
                pos1.append(i)
            if word == word2:
                pos2.append(i)

        # Step 2: Find minimum distance
        min_distance = float('inf')
        if word1 == word2:
            for i in range(len(pos1)):
                for j in range(i + 1, len(pos1)):
                    distance = abs(pos1[i] - pos1[j])
                    min_distance = min(min_distance, distance)
        else:
            for p1 in pos1:
                for p2 in pos2:
                    distance = abs(p1 - p2)
                    min_distance = min(min_distance, distance)

        # Step 3: Return result
        return min_distance

• Time Complexity: O(n²)—checking all pairs.
• Space Complexity: O(n)—storing positions.

It’s intuitive but less efficient.

Comparing the Two Solutions

• Best Solution (Two-Pointer):
• Pros: O(n) time, minimal space, handles both cases.
• Cons: Requires position-tracking logic.
• Alternative Solution (Brute Force):
• Pros: Simple, shows all pairs.
• Cons: O(n²) time, more space.

Two-pointer wins for speed.

Additional Examples and Edge Cases

Same Word, Adjacent

• ["a", "a"], word1 = "a", word2 = "a" → 1

Different Words

• ["a", "b"], word1 = "a", word2 = "b" → 1

Multiple Gaps

• ["a", "b", "a"], word1 = "a", word2 = "a" → 2

Both solutions manage these well.

Complexity Breakdown

• Two-Pointer:
• Time: O(n)—single pass.
• Space: O(1)—tiny footprint.
• Brute Force:
• Time: O(n²)—pairwise checks.
• Space: O(n)—position lists.

Two-pointer excels.

Key Takeaways for Beginners

• Two-Pointer: Track latest positions for speed.
• Same Word: Shift positions cleverly.
• Brute Force: Easy but slow.
• Python Tip: Conditionals are key—see [Python Basics](/python/basics).

Final Thoughts: Close the Gap Like a Pro

LeetCode 245: Shortest Word Distance III in Python adds a fun twist to distance problems. The two-pointer solution shines with O(n) efficiency, while brute force offers a clear starting point. Want more? Try LeetCode 243: Shortest Word Distance or LeetCode 244: Shortest Word Distance II. Ready to measure? Head to Solve LeetCode 245 on LeetCode and find those distances today!