LeetCode 408: Valid Word Abbreviation Solution in Python – A Step-by-Step Guide

What Is LeetCode 408: Valid Word Abbreviation?

In LeetCode 408: Valid Word Abbreviation, you’re given two strings: word (the full word, like "internationalization") and abbr (its abbreviation, like "i18n"). The abbreviation can use numbers to represent how many characters are skipped (e.g., "18" means skip 18 letters), but it can’t have leading zeros or skip the whole word. Your task is to return True if abbr is a valid abbreviation of word, False otherwise. For example, "i18n" matches "internationalization" (i, skip 18, n), but "1n" doesn’t (skips too much).

Problem Statement

• Input: Two strings: word and abbr.
• Output: A boolean—True if abbr validly abbreviates word, False otherwise.
• Rules:
• Numbers in abbr count skipped characters in word.
• No leading zeros in numbers (e.g., "01" invalid).
• Literal characters must match exactly.
• Abbreviation must cover the full word length.

Constraints

• 1 <= word.length <= 20.
• 1 <= abbr.length <= 10.
• word contains only lowercase letters.
• abbr contains lowercase letters and digits.

Examples

• Input: word = "internationalization", abbr = "i18n"
• Output: True (i, skip 18, n matches).
• Input: word = "apple", abbr = "a2e"
• Output: False (a, skip 2, e skips too much).
• Input: word = "a", abbr = "01"
• Output: False (leading zero invalid).

Understanding the Problem: Matching the Shortcut

To solve LeetCode 408: Valid Word Abbreviation in Python, we need to check if abbr correctly shortens word by matching letters and skipping the right number of characters with numbers. A naive idea might be to expand the abbreviation and compare—but that’s clunky! Instead, we’ll use:

• Best Solution (Two-Pointer Iteration): O(n) time (n = max(word length, abbr length)), O(1) space—steps through both strings.
• Alternative Solution (Recursive): O(n) time, O(n) space—breaks it down recursively.

Let’s dive into the two-pointer solution with a clear, step-by-step explanation.

Best Solution: Two-Pointer Iteration

Why This Is the Best Solution

The two-pointer iteration method is the top pick because it’s fast—O(n) time, O(1) space—and super straightforward. It uses two pointers to walk through word and abbr together, matching letters and handling numbers as skips, all in one pass. It’s like reading both the full book and its summary side-by-side, checking they line up!

How It Works

Think of word and abbr as two paths you’re walking:

• Step 1: Set Up Pointers:
• One pointer (i) for word, one (j) for abbr.
• Step 2: Walk and Match:
• If abbr[j] is a letter, it must match word[i], move both pointers.
• If abbr[j] is a digit:
• Build the full number (e.g., "18" from "1" then "8").
• Skip that many characters in word (move i).
• Step 3: Check Rules:
• No leading zeros (e.g., "01" fails).
• Final positions must match word length.
• Step 4: Why This Works:
• Pointers keep both strings in sync, ensuring skips and matches align.
• Single pass avoids extra storage or backtracking.
• It’s like following a treasure map where numbers jump you ahead!

Step-by-Step Example

Example: word = "internationalization", abbr = "i18n"

• Start: i=0 (w), j=0 (a).
• j=0: "i" matches "i", i=1, j=1.
• j=1: "1", num=1, j=2.
• j=2: "8", num=18, j=3, skip 18 in word, i=19.
• j=3: "n" matches "n" (i=19), i=20, j=4.
• End: j=4 (len=4), i=20 (len=20), matches ✓.
• Result: True.

Example: word = "apple", abbr = "a2e"

• Start: i=0, j=0.
• j=0: "a" matches "a", i=1, j=1.
• j=1: "2", num=2, i=3, j=2.
• j=2: "e" matches "l" (i=3), fails.
• Result: False.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

Copy codeclass Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        # Step 1: Set pointers
        i = 0  # word pointer
        j = 0  # abbr pointer

        # Step 2: Walk through both strings
        while j < len(abbr):
            # If letter, must match
            if abbr[j].isalpha():
                if i >= len(word) or word[i] != abbr[j]:
                    return False
                i += 1
                j += 1
            # If digit, build number and skip
            elif abbr[j].isdigit():
                # Check for leading zero
                if abbr[j] == "0" and (j == 0 or not abbr[j-1].isdigit()):
                    return False
                num = 0
                while j < len(abbr) and abbr[j].isdigit():
                    num = num * 10 + int(abbr[j])
                    j += 1
                i += num  # Skip num characters in word
                if i > len(word):  # Skipped too far
                    return False

        # Step 3: Check if we covered the whole word
        return i == len(word)

• Line 4-5: Start pointers at 0 for both strings.
• Line 8-22: Loop through abbr:
• Line 9-13: If letter:
• Check if word is out of bounds or doesn’t match, fail.
• Move both pointers (e.g., "i" matches "i", i=1, j=1).
• Line 14-22: If digit:
• Line 16-17: Fail if leading zero (e.g., "01" or "a01b").
• Line 18-21: Build number (e.g., "18" → 18), advance j.
• Line 22: Skip in word (i += 18), fail if overshoot.
• Line 25: Success if i matches word length (all covered).
• Time Complexity: O(n)—single pass, n = max(word length, abbr length).
• Space Complexity: O(1)—just pointers and a number.

This is like matching a shorthand note to the full story in one go!

Alternative Solution: Recursive Approach

Why an Alternative Approach?

The recursive method breaks the problem into smaller chunks, checking each part of abbr against word. It’s O(n) time and O(n) space (recursion stack)—less efficient but a different angle. It’s like peeling the abbreviation layer by layer to see if it fits!

How It Works

Picture it as a step-by-step unraveling:

• Step 1: Base case: both strings empty, True.
• Step 2: If abbr starts with a letter, match and recurse.
• Step 3: If abbr starts with a digit, parse number, skip, recurse.
• Step 4: Fail if rules break (leading zero, mismatch).

Step-by-Step Example

Example: word = "apple", abbr = "a2e"

• (apple, a2e): "a" matches, recurse (pple, 2e).
• (pple, 2e): Skip 2, recurse (le, e).
• (le, e): "e" vs "l", fails.
• Result: False.

Code for Recursive Approach

Copy codeclass Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        def check(w_idx, a_idx):
            # Base case: both exhausted
            if w_idx == len(word) and a_idx == len(abbr):
                return True
            if w_idx >= len(word) or a_idx >= len(abbr):
                return False

            # Letter case
            if abbr[a_idx].isalpha():
                if word[w_idx] != abbr[a_idx]:
                    return False
                return check(w_idx + 1, a_idx + 1)

            # Number case
            if abbr[a_idx] == "0" and (a_idx == 0 or not abbr[a_idx-1].isdigit()):
                return False
            num = 0
            while a_idx < len(abbr) and abbr[a_idx].isdigit():
                num = num * 10 + int(abbr[a_idx])
                a_idx += 1
            return check(w_idx + num, a_idx)

        return check(0, 0)

• Time Complexity: O(n)—processes each character once.
• Space Complexity: O(n)—recursion stack.

It’s a recursive unraveling of the shortcut!

Comparing the Two Solutions

• Two-Pointer Iteration (Best):
• Pros: O(n), O(1), fast and clean.
• Cons: Less flexible.
• Recursive (Alternative):
• Pros: O(n), O(n), intuitive breakdown.
• Cons: Stack space.

Two-pointer wins for efficiency.

Additional Examples and Edge Cases

• "a", "a": True.
• "ab", "a1": True.
• "word", "w0rd": False (leading zero).

Two-pointer handles all.

Complexity Breakdown

• Two-Pointer Iteration: Time O(n), Space O(1).
• Recursive: Time O(n), Space O(n).

Two-pointer’s lean.

Key Takeaways

• Two-Pointer: Step in sync!
• Recursive: Break it down!
• Strings: Numbers twist it.
• Python Tip: Pointers rock—see [Python Basics](/python/basics).

Final Thoughts: Validate That Abbrev

LeetCode 408: Valid Word Abbreviation in Python is a string-matching adventure. Two-pointer iteration zips through it, while recursive peels it apart. Want more string fun? Try LeetCode 10: Regular Expression Matching or LeetCode 415: Add Strings. Ready to shorten? Head to Solve LeetCode 408 on LeetCode and check those abbreviations today!