9197bbc079a9-valid-word-abbr

Problem Statement

A string can be abbreviated by replacing any number of non-adjacent, non-empty substrings with their lengths. The lengths should not have leading zeros.

For example, a string such as "substitution" could be abbreviated as (but not limited to):

  • "s10n" ("s ubstitutio n")
  • "sub4u4" ("sub stit u tion")
  • "12" ("substitution")
  • "su3i1u2on" ("su bst i t u ti on")
  • "substitution" (no substrings replaced)

The following are not valid abbreviations:

  • "s55n" ("s ubsti tutio n", the replaced substrings are adjacent)
  • "s010n" (has leading zeros)
  • "s0ubstitution" (replaces an empty substring)

Example 1:

Input: word = "internationalization", abbr = "i12iz4n"
Output: true

Example 2:

Input: word = "apple", abbr = "a2e"
Output: false

Constraints:

  • 1 <= word.length <= 20
  • 1 <= abbr.length <= 10
  • abbr consists of lowercase English letters and digits.
  • No leading zeros in numbers.

Approach

This is a two-pointer problem where we traverse both word and abbr simultaneously. The key challenges:

  1. Extracting numbers correctly while avoiding leading zeros.
  2. Advancing pointers properly for both word and abbr.
  3. Ensuring character matches where applicable.

Python Solution

class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        word_ptr, abbr_ptr = 0, 0

        while word_ptr < len(word) and abbr_ptr < len(abbr):
            if abbr[abbr_ptr].isdigit():
                # Leading zeros are invalid
                if abbr[abbr_ptr] == "0":
                    return False
                
                num = 0
                while abbr_ptr < len(abbr) and abbr[abbr_ptr].isdigit():
                    # right now leading is nonzero, we can form number as long as
                    # next char is digit
                    num = num * 10 + int(abbr[abbr_ptr])
                    abbr_ptr += 1
                
                word_ptr += num
            else:
                # if the character doesn't match or run out of chars , return False
                if word_ptr >= len(word) or word[word_ptr] != abbr[abbr_ptr]:
                    return False
                word_ptr += 1
                abbr_ptr += 1

        return word_ptr == len(word) and abbr_ptr == len(abbr)

Time & Space Complexity

  • Time Complexity: \( O(n) \), where \( n \) is the length of abbr. Each character in abbr is processed once.
  • Space Complexity: \( O(1) \), since only a few pointers and an integer variable are used.

Edge Cases to Consider

✅ "substitution", "s10n" → ✅ Valid
✅ "substitution", "s55n" → ❌ Invalid (adjacent abbreviations)
✅ "substitution", "s010n" → ❌ Invalid (leading zero)
✅ "apple", "a2e" → ❌ Invalid (wrong abbreviation)
✅ "apple", "a5" → ✅ Valid

Final Thoughts

This is an “Easy” problem, but string parsing problems often require careful handling of edge cases. 🚀 Mastering these small but tricky cases helps in real-world coding interviews.