We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Valid Word Abbreviation

Number: 408

Difficulty: Easy

Paid? Yes

Companies: Meta, Datadog, Amazon, Snowflake, TikTok, Google

Problem Description

Given a string word and an abbreviation abbr, determine if the abbreviation is a valid representation of the word. In the abbreviation, digits represent the number of characters to skip in word. The number in the abbreviation must not have leading zeros and should represent a non-empty substring of the word. The letters in the abbreviation must match exactly the corresponding letters in the word.

Key Insights

  • Use two pointers: one for looping through the word and one for the abbreviation.
  • When encountering a digit in abbr, accumulate the number and skip that many characters in the word.
  • Check for invalid cases such as numbers with leading zeros or consecutive digit segments that might imply adjacent skipped substrings.
  • Compare letters directly when they are not digits.

Space and Time Complexity

Time Complexity: O(n + m) where n is the length of the word and m is the length of the abbreviation. Space Complexity: O(1) (constant extra space)

Solution

The approach uses two pointers to iterate over the word and abbreviation. For each character in the abbreviation:

  • If it is a letter, compare it with the current character in the word.
  • If it is a digit, first ensure that it does not start with '0'. Then, convert the sequence of digits into a number which represents how many characters in the word to skip. After processing, both pointers should have reached the end of their respective strings for the abbreviation to be valid. This approach is efficient due to its linear pass with constant extra space.

Code Solutions

# Python solution for valid word abbreviation

def validWordAbbreviation(word: str, abbr: str) -> bool:
    word_index = 0  # pointer for the word
    abbr_index = 0  # pointer for the abbreviation
    
    while abbr_index < len(abbr):
        # if current abbrev char is a digit
        if abbr[abbr_index].isdigit():
            # leading zero check: if the digit is '0', it is invalid
            if abbr[abbr_index] == '0':
                return False
            # build the entire number
            num = 0
            while abbr_index < len(abbr) and abbr[abbr_index].isdigit():
                num = num * 10 + int(abbr[abbr_index])
                abbr_index += 1
            # skip num characters in word
            word_index += num
        else:
            # if letter doesn't match or word index is out of bounds, invalid
            if word_index >= len(word) or word[word_index] != abbr[abbr_index]:
                return False
            word_index += 1
            abbr_index += 1
    
    # Valid if and only if the entire word was covered
    return word_index == len(word)

# Example usage:
#print(validWordAbbreviation("internationalization", "i12iz4n"))  # Expected output: True
#print(validWordAbbreviation("apple", "a2e"))  # Expected output: False
← Back to All Questions