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

What Is LeetCode 243: Shortest Word Distance?

In LeetCode 243: Shortest Word Distance, you’re given a list of words (wordsDict) and two specific words (word1 and word2). Your task is to find the shortest distance between any occurrence of word1 and word2 in the list, measured as the number of words between them. This problem is simpler than array manipulations like LeetCode 238: Product of Array Except Self, focusing on positional tracking.

Problem Statement

• Input: A list of strings wordsDict and two strings word1 and word2.
• Output: An integer representing the minimum distance between word1 and word2.
• Rules: Distance is the absolute difference between indices of the words; word1 and word2 are distinct and present in the list.

Constraints

• List length: 2 to 10^4.
• Word length: 1 to 10 characters.
• All words are lowercase; word1 ≠ word2.

Examples

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

Understanding the Problem: Measuring Word Gaps

To solve LeetCode 243: Shortest Word Distance in Python, we need to find the smallest gap between any pair of positions where word1 and word2 appear in the list. A basic approach—checking every possible pair of positions—works but is slow. Instead, we’ll use two methods: 1. Best Solution (Two-Pointer): O(n) time, O(1) space—fast and efficient. 2. Alternative Solution (Brute Force): O(n²) time, O(1) space—simple but less optimal.

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 champion for LeetCode 243 because it scans the list just once, keeping track of the latest positions of word1 and word2, and updates the minimum distance on the fly. It’s super fast (O(n) time) and uses almost no extra space (O(1)), making it perfect for this problem.

How It Works (Super Detailed for Beginners)

Imagine you’re walking through the list of words with two sticky notes: one labeled "word1’s last spot" and one labeled "word2’s last spot." Every time you find one of your target words, you move its sticky note to that spot. If you’ve seen both words at least once (both sticky notes are placed), you measure the distance between them and keep track of the smallest distance you’ve found so far. Here’s how it works step-by-step:

• Set Up: Start with two variables, pos1 and pos2, to remember the last positions of word1 and word2. Set them to -1 at first because we haven’t found the words yet. Also, keep a min_distance variable to store the smallest gap, starting with a really big number (like infinity) so any real distance will be smaller.
• Walk the List: Go through the list one word at a time, checking each word’s position (its index).
• If the word is word1, update pos1 to the current index.
• If the word is word2, update pos2 to the current index.
• Measure When Ready: After updating a position, check if both pos1 and pos2 are set (not -1). If they are, calculate the distance between them using abs(pos1 - pos2) (absolute difference, since we don’t care which comes first). If this distance is smaller than min_distance, update min_distance.
• Finish: After checking all words, min_distance holds the answer.

This method is like keeping your eyes peeled for both words and measuring the gap whenever you’ve spotted them both—it’s simple once you get the hang of it!

Step-by-Step Example

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

• Setup: pos1 = -1 (for "coding"), pos2 = -1 (for "practice"), min_distance = infinity.
• Index 0: "practice"
• Matches word2, so pos2 = 0.
• pos1 = -1, pos2 = 0—only one found, no distance yet.
• Index 1: "makes"
• No match, pos1 = -1, pos2 = 0.
• Index 2: "perfect"
• No match, pos1 = -1, pos2 = 0.
• Index 3: "coding"
• Matches word1, so pos1 = 3.
• pos1 = 3, pos2 = 0—both found! Distance = abs(3 - 0) = 3.
• min_distance = 3.
• Index 4: "makes"
• No match, pos1 = 3, pos2 = 0, min_distance = 3.
• Result: min_distance = 3.

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

• Setup: pos1 = -1 (for "makes"), pos2 = -1 (for "coding"), min_distance = infinity.
• Index 0: "practice"
• No match, pos1 = -1, pos2 = -1.
• Index 1: "makes"
• Matches word1, pos1 = 1.
• pos1 = 1, pos2 = -1.
• Index 2: "perfect"
• No match, pos1 = 1, pos2 = -1.
• Index 3: "coding"
• Matches word2, pos2 = 3.
• pos1 = 1, pos2 = 3—both found! Distance = abs(1 - 3) = 2.
• min_distance = 2.
• Index 4: "makes"
• Matches word1, pos1 = 4.
• pos1 = 4, pos2 = 3—both found! Distance = abs(4 - 3) = 1.
• Update min_distance = 1.
• Result: min_distance = 1.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down 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
        pos2 = -1  # Last position of word2
        min_distance = float('inf')  # Start with a huge number

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

            # Step 3: Update positions
            if current_word == word1:
                pos1 = i  # Move word1’s sticky note here
            elif current_word == word2:
                pos2 = i  # Move word2’s sticky note here

            # Step 4: Measure distance if we’ve seen both
            if pos1 != -1 and pos2 != -1:
                distance = abs(pos1 - pos2)  # How far apart are they?
                min_distance = min(min_distance, distance)  # Keep the smallest

        # Step 5: Return the smallest distance found
        return min_distance

• Time Complexity: O(n)—we only go through the list once.
• Space Complexity: O(1)—just a few variables, no extra storage.

This solution is like a treasure hunt where you only need to remember the last place you saw each clue—it’s quick and easy once you understand it!

Alternative Solution: Brute Force Approach

Why an Alternative Approach?

The brute force approach is like checking every possible pair of hiding spots for your two words. It’s not the fastest, but it’s super simple to understand—perfect for beginners who want to see every step clearly before moving to the optimized method.

How It Works

• Find all positions of word1 and word2 in the list.
• Calculate the distance between every pair of their positions.
• Pick the smallest distance.

Step-by-Step Example

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

• Positions:
• "makes": [1, 4]
• "coding": [3]
• Pairs:
• (1, 3): abs(1 - 3) = 2
• (4, 3): abs(4 - 3) = 1
• Output: Smallest = 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_list = []
        pos2_list = []
        for i, word in enumerate(wordsDict):
            if word == word1:
                pos1_list.append(i)
            elif word == word2:
                pos2_list.append(i)

        # Step 2: Find minimum distance between all pairs
        min_distance = float('inf')
        for p1 in pos1_list:
            for p2 in pos2_list:
                distance = abs(p1 - p2)
                min_distance = min(min_distance, distance)

        # Step 3: Return result
        return min_distance

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

It’s clear but less efficient.

Comparing the Two Solutions

• Best Solution (Two-Pointer):
• Pros: O(n) time, minimal space, beginner-friendly once explained.
• Cons: Requires understanding of tracking positions.
• Alternative Solution (Brute Force):
• Pros: Very intuitive, shows all steps.
• Cons: O(n²) time, not scalable.

The two-pointer method wins for speed.

Additional Examples and Edge Cases

Adjacent Words

• Input: ["a", "b"], word1 = "a", word2 = "b"
• Output: 1

Multiple Occurrences

• Input: ["a", "b", "a"], word1 = "a", word2 = "b"
• Output: 1

Far Apart

• Input: ["a", "x", "y", "z", "b"], word1 = "a", word2 = "b"
• Output: 4

Both solutions handle 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 is the clear winner.

Key Takeaways for Beginners

• Two-Pointer: Track latest positions for efficiency.
• Distance: Use abs() for absolute gaps.
• Brute Force: Good for learning, slow for big lists.
• Python Tip: Loops are powerful—see [Python Basics](/python/basics).

Final Thoughts: Measure Distances Like a Pro

LeetCode 243: Shortest Word Distance in Python is a great way to practice list traversal. The two-pointer solution offers O(n) brilliance, while brute force provides a simple starting point. Want more? Try LeetCode 244: Shortest Word Distance II or LeetCode 245: Shortest Word Distance III. Ready to measure? Head to Solve LeetCode 243 on LeetCode and find those gaps today!