💬 Discord
Sign In
NeetCode #179LC-408EasyTwo Pointers
← Back to All Problems

#179 · #408 · Valid Word Abbreviation(有效单词缩写)

📌 Problem Statement & Constraints

A string can be abbreviated by replacing any number of non-adjacent, non-empty substrings with their lengths. Given a string word and an abbreviation abbr, return whether abbr is a valid abbreviation of word. Constraints: 1 <= word.length <= 20, 1 <= abbr.length <= 10.

💡 Core Algorithmic Approaches

  1. Walk both strings with two pointers.
  2. When the abbreviation character is a digit, parse the whole number (multi-digit numbers are allowed) and advance the word pointer by that many characters.
  3. Leading zeros are invalid: a number like 01 is not a legal abbreviation.
  4. When the character is a letter, it must match the current word character exactly.

💻 Benchmark Python3 Implementation

class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        i = j = 0
        while i < len(word) and j < len(abbr):
            if abbr[j].isdigit():
                if abbr[j] == "0":         # leading zero is invalid
                    return False
                num = 0
                while j < len(abbr) and abbr[j].isdigit():
                    num = num * 10 + int(abbr[j])
                    j += 1
                i += num                   # skip that many word characters
            else:
                if word[i] != abbr[j]:
                    return False
                i += 1
                j += 1
        return i == len(word) and j == len(abbr)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(max(|word|, |abbr|)): each pointer advances monotonically.
💾 Space Complexity
O(1): two indices.

⚠️ Interview Pitfalls & Follow-ups

  • Treating each digit as a separate one-character skip: abbr = "12" means skip 12 characters, not 1 then 2.
  • Allowing leading zeros: abbr = "01" is invalid even though it parses to 1.
  • Not checking that both pointers reach the end: a valid abbreviation must consume both strings entirely.
  • Skipping past the end of word: the i += num may exceed the length, which the final check catches, but it must not index out of range during the loop.