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

What Is LeetCode 244: Shortest Word Distance II?

In LeetCode 244: Shortest Word Distance II, you’re tasked with creating a class WordDistance that takes a list of words (wordsDict) in its constructor and provides a method shortest(word1, word2) to return the minimum distance between word1 and word2 in the list. Unlike LeetCode 243: Shortest Word Distance, which handles a single query, this problem requires efficient handling of multiple queries, making preprocessing key.

Problem Statement

• Constructor: WordDistance(wordsDict)—initialize with a word list.
• Method: shortest(word1, word2)—return the minimum distance between word1 and word2.
• Rules: Distance is the absolute difference between indices; words may appear multiple times; word1 and word2 are distinct and present in the list.

Constraints

• List length: 2 to 3 * 10^4.
• Word length: 1 to 10 characters.
• All words are lowercase.
• shortest called 1 to 10^4 times.

Examples

• Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"]
• shortest("coding", "practice") → 3 (indices 3 and 0).
• shortest("makes", "coding") → 1 (indices 1 and 3, or 4 and 3).
• Input: wordsDict = ["a", "b", "c", "a"]
• shortest("a", "b") → 1 (indices 0 and 1).

Understanding the Problem: Multiple Distance Queries

To solve LeetCode 244: Shortest Word Distance II in Python, we need a system that preprocesses the word list once and then answers multiple distance queries quickly. A naive approach—scanning the list for each query—works for one-off cases but is too slow for repeated calls. Instead, we’ll use two methods: 1. Best Solution (Hash Map with Two-Pointer): O(n) preprocessing, O(k1 + k2) per query—fast and optimized. 2. Alternative Solution (Brute Force with Positions): O(n) preprocessing, O(k1 * k2) per query—simpler but slower.

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

Best Solution: Hash Map with Two-Pointer Approach

Why This Is the Best Solution

The hash map with two-pointer approach is the star of LeetCode 244 because it preprocesses the word list in O(n) time to store word positions, then answers each query in O(k1 + k2) time (where k1 and k2 are the number of occurrences of the two words). It’s efficient for multiple queries and uses reasonable space, making it the go-to solution.

How It Works (Super Detailed for Beginners)

Think of this solution as setting up a filing cabinet for a library. First, you organize all the books (words) by title and note down every page (index) where each title appears. Then, when someone asks, “How close are these two books?” you pull out their page lists and find the smallest gap between any pair of pages. Here’s how it works, step-by-step, in a way anyone can follow:

• Step 1: Build the Filing Cabinet (Constructor):
• Take the list of words and create a dictionary (hash map) where each word is a key, and its value is a list of all the indices where it appears.
• For example, if "makes" is at positions 1 and 4, the dictionary entry is "makes": [1, 4].
• You only do this once when the class is created, so it’s ready for any questions later.

• Step 2: Answer Questions (Shortest Method):
• When someone asks for the distance between word1 and word2, grab their index lists from the dictionary.
• Now, imagine you have two rulers—one for word1’s positions and one for word2’s. You want to find the smallest distance between any mark on one ruler and any mark on the other.
• Since the lists are sorted (because we went through the word list in order), use two pointers—like two fingers pointing at positions:
• Start with one finger (p1) at the first position of word1 and another (p2) at the first position of word2.
• Calculate the distance between these positions with abs(p1 - p2).
• Move the finger pointing to the smaller number forward (if p1 < p2, move p1; if p2 < p1, move p2).
• Keep track of the smallest distance you find.
• Stop when you run out of positions in either list.

• Why It Works: By moving the pointer at the smaller index, you’re always checking the next closest pair without missing any possibilities. It’s like sliding along a number line, looking for the tightest squeeze between two sets of points.

Step-by-Step Example

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

• Constructor:
• Build hash map:
• "practice": [0]
• "makes": [1, 4]
• "perfect": [2]
• "coding": [3]

• Query 1: shortest("coding", "practice")
• Lists: "coding": [3], "practice": [0]
• Pointers: p1 = 0 (index 3), p2 = 0 (index 0)
• Distance: abs(3 - 0) = 3
• Only one pair possible, so result = 3.

• Query 2: shortest("makes", "coding")
• Lists: "makes": [1, 4], "coding": [3]
• Pointers: p1 = 0 (index 1), p2 = 0 (index 3)
• Distance: abs(1 - 3) = 2, min = 2
• Move p1 (1 < 3): p1 = 1 (index 4), p2 = 0 (index 3)
• Distance: abs(删:4 - 3) = 1, min = 1
• p1 out of bounds, stop. Result = 1.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass WordDistance:
    def __init__(self, wordsDict: List[str]):
        # Step 1: Create our filing cabinet (dictionary)
        self.word_positions = {}
        # Step 2: Fill it with word positions
        for i, word in enumerate(wordsDict):
            if word in self.word_positions:
                self.word_positions[word].append(i)  # Add position
            else:
                self.word_positions[word] = [i]  # Start new list

    def shortest(self, word1: str, word2: str) -> int:
        # Step 3: Get position lists from the cabinet
        pos1 = self.word_positions[word1]
        pos2 = self.word_positions[word2]

        # Step 4: Set up our two fingers (pointers)
        p1 = 0
        p2 = 0
        min_distance = float('inf')  # Start with a huge number

        # Step 5: Slide pointers to find smallest gap
        while p1 < len(pos1) and p2 < len(pos2):
            distance = abs(pos1[p1] - pos2[p2])  # Measure gap
            min_distance = min(min_distance, distance)  # Update if smaller
            # Step 6: Move the smaller pointer
            if pos1[p1] < pos2[p2]:
                p1 += 1  # Move word1’s pointer
            else:
                p2 += 1  # Move word2’s pointer

        # Step 7: Return the smallest distance
        return min_distance

• Constructor Time: O(n)—one pass to build the map.
• Query Time: O(k1 + k2)—where k1 and k2 are the lengths of the position lists.
• Space Complexity: O(n)—storing all positions.

This solution is like a librarian who’s ready to answer questions in a snap!

Alternative Solution: Brute Force with Precomputed Positions

Why an Alternative Approach?

The brute force approach precomputes positions like the best solution but checks every possible pair for each query. It’s simpler to understand—no pointers sliding around—but slower, making it great for learning the basics.

How It Works

• Constructor: Build a hash map of word positions.
• Shortest: For each query, compare all pairs of positions between word1 and word2 to find the minimum distance.

Step-by-Step Example

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

• Constructor: Same hash map as above.
• Query: shortest("makes", "coding")
• "makes": [1, 4], "coding": [3]
• Pairs: (1, 3) → 2, (4, 3) → 1
• Result: 1.

Code for Brute Force Approach

Copy codeclass WordDistance:
    def __init__(self, wordsDict: List[str]):
        self.word_positions = {}
        for i, word in enumerate(wordsDict):
            if word in self.word_positions:
                self.word_positions[word].append(i)
            else:
                self.word_positions[word] = [i]

    def shortest(self, word1: str, word2: str) -> int:
        pos1 = self.word_positions[word1]
        pos2 = self.word_positions[word2]
        min_distance = float('inf')
        for p1 in pos1:
            for p2 in pos2:
                distance = abs(p1 - p2)
                min_distance = min(min_distance, distance)
        return min_distance

• Constructor Time: O(n)—same preprocessing.
• Query Time: O(k1 * k2)—all pairs checked.
• Space Complexity: O(n)—position storage.

It’s straightforward but less efficient.

Comparing the Two Solutions

• Best Solution (Hash Map with Two-Pointer):
• Pros: Fast queries (O(k1 + k2)), scalable.
• Cons: Slightly trickier with pointers.
• Alternative Solution (Brute Force):
• Pros: Easy to follow, no pointer logic.
• Cons: Slower queries (O(k1 * k2)).

The two-pointer method shines for multiple queries.

Additional Examples and Edge Cases

Single Occurrence

• ["a", "b"], shortest("a", "b") → 1

Multiple Occurrences

• ["a", "b", "a"], shortest("a", "b") → 1

Far Apart

• ["a", "x", "y", "b"], shortest("a", "b") → 3

Both handle these well.

Complexity Breakdown

• Best Solution:
• Constructor: O(n)
• Query: O(k1 + k2)
• Space: O(n)
• Brute Force:
• Constructor: O(n)
• Query: O(k1 * k2)
• Space: O(n)

Best solution wins on query speed.

Key Takeaways for Beginners

• Hash Map: Store positions for quick lookup.
• Two-Pointer: Slide along sorted lists for efficiency.
• Brute Force: Check everything—simple but slow.
• Python Tip: Dictionaries are awesome—see [Python Basics](/python/basics).

Final Thoughts: Query Distances Like a Pro

LeetCode 244: Shortest Word Distance II in Python is a fantastic step up from single queries. The hash map with two-pointer solution offers query-speed brilliance, while brute force provides a clear starting point. Want more? Try LeetCode 243: Shortest Word Distance or LeetCode 245: Shortest Word Distance III. Ready to build your word finder? Head to Solve LeetCode 244 on LeetCode and start measuring today!