Domain 1EasyCORE

Valid Word Abbreviation

The problem asks us to determine whether a given string `s` matches an abbreviation `abbr`. An abbreviation can contain lowercase letters and digits, where digits represent consecutive groups of characters in the original string that are omitted. The task is to verify if the abbreviation correctly represents the original string.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

408. Valid Word Abbreviation

Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 31.5%


Problem Breakdown

The problem asks us to determine whether a given string s matches an abbreviation abbr. An abbreviation can contain lowercase letters and digits, where digits represent consecutive groups of characters in the original string that are omitted. The task is to verify if the abbreviation correctly represents the original string.

Inputs:

  • s: A non-empty string containing only lowercase letters.
  • abbr: A string containing only lowercase letters and digits.

Outputs:

  • A boolean value indicating whether abbr is a valid abbreviation of s.

Implicit Constraints or Tricky Edge Cases:

  • The abbreviation can start with a digit, which means the original string must have at least that many characters.
  • Multiple consecutive digits in the abbreviation are not allowed (e.g., “a12b” is invalid).
  • An empty abbreviation is considered valid for any non-empty string.

Intuition

A brute-force approach would involve generating all possible abbreviations of s and checking if abbr matches any of them. However, this approach is impractical due to its exponential time complexity.

The key insight is to use a two-pointer technique to traverse both the original string s and the abbreviation abbr. By carefully handling digits in abbr, we can determine if it correctly represents s.

Approach

  1. Initialize two pointers, i for s and j for abbr.
  2. Traverse through both strings:
    • If abbr[j] is a digit, accumulate the number represented by consecutive digits.
    • Move the pointer i in s by the accumulated number of characters.
    • If abbr[j] is a letter, check if it matches s[i]. If not, return False.
  3. After processing both strings, ensure that all characters in both have been processed correctly.

Complexity Analysis

  • Time Complexity: O(n + m), where n is the length of s and m is the length of abbr. We traverse each string once.
  • Space Complexity: O(1). We use a constant amount of extra space for variables.

Solution

def validWordAbbreviation(s: str, abbr: str) -> bool:
    i, j = 0, 0
    while i < len(s) and j < len(abbr):
        if abbr[j].isdigit():
            # Handle multiple digits
            if abbr[j] == '0':
                return False  # Leading zero is invalid
            num = 0
            while j < len(abbr) and abbr[j].isdigit():
                num = num * 10 + int(abbr[j])
                j += 1
            i += num
        else:
            if s[i] != abbr[j]:
                return False
            i += 1
            j += 1
    
    # Ensure both strings are fully traversed
    return i == len(s) and j == len(abbr)

Edge Cases Handled

  • Leading zeros in abbr: The code returns False if a digit starts with ‘0’.
  • Empty abbreviation: If abbr is empty, it will not match any non-empty s.
  • Mismatched lengths after processing: The final check ensures both strings are fully traversed.
  • Consecutive digits in abbr: The code accumulates digits correctly and skips the corresponding number of characters in s.