Problem Description

Given a string word and an abbreviation abbr, determine if the abbreviation is valid for the given word.

An abbreviation is formed by replacing any number of non-adjacent, non-empty substrings with their lengths. The key rules are:

1. Non-adjacent substrings: You cannot replace two consecutive substrings with numbers. For example, "s55n" is invalid for "substitution" because it tries to replace two adjacent substrings ("ubsti" and "tutio").

2. Non-empty substrings: You cannot replace an empty substring. Numbers must be at least 1.

3. No leading zeros: Numbers cannot have leading zeros. For example, "s010n" is invalid.

4. Mixed format: An abbreviation can contain both letters from the original word and numbers representing the length of replaced substrings.

Examples of valid abbreviations for "substitution":

• "s10n" - keeps 's' and 'n', replaces the middle 10 characters
• "sub4u4" - keeps "sub", replaces 4 characters, keeps "u", replaces 4 characters
• "12" - replaces all 12 characters
• "substitution" - no replacements, the full word itself

Examples of invalid abbreviations:

• "s55n" - adjacent replacements (5 and 5 are next to each other)
• "s010n" - leading zero in the number 010
• "s0ubstitution" - tries to replace 0 characters (empty substring)

The task is to verify if a given abbreviation correctly matches the original word by checking if the letters match at their positions and the numbers correctly represent the count of skipped characters.

Intuition

The key insight is that we need to traverse both strings simultaneously and verify that they match according to the abbreviation rules. Think of it like following a set of instructions where letters tell us to match exactly, and numbers tell us to skip ahead.

When we encounter a letter in abbr, it must match the corresponding position in word. When we encounter a number, it tells us how many characters to skip in word. The challenge is handling multi-digit numbers correctly.

Consider the example: word = "substitution" and abbr = "s10n". We need to:

1. Match 's' at position 0
2. Skip 10 characters (the number 10 tells us this)
3. Match 'n' at position 11

This suggests using two pointers - one for each string. The pointer in word advances either by 1 (when matching a letter) or by the number value (when we see digits in abbr). The pointer in abbr always advances by 1.

For multi-digit numbers, we need to accumulate the value. When we see '1' followed by '0', we should interpret this as 10, not as separate values. So we build the number: x = x * 10 + digit.

The tricky part is validating the rules:

• Leading zeros: Check if the first digit is '0' when starting a new number (x == 0 and abbr[j] == '0')
• Non-adjacent replacements: This is automatically handled since after processing a number, we must encounter a letter before the next number
• Bounds checking: Ensure we don't skip beyond the word's length

At the end, both strings should be fully consumed. The word pointer plus any remaining skip count should equal the word's length, and the abbreviation pointer should reach the end.

Solution Approach

We use a two-pointer simulation approach to validate the abbreviation. The algorithm maintains:

• Pointer i for traversing the word
• Pointer j for traversing the abbr
• Variable x to accumulate multi-digit numbers

Step-by-step implementation:

1. Initialize pointers and accumulator: Start with i = j = x = 0. These track our positions in both strings and any number being built.

2. Main loop: While both i < m and j < n (where m and n are lengths of word and abbr):

   Case 1: Current character in abbr is a digit

   • Check for leading zeros: If abbr[j] == '0' and x == 0, this is an invalid leading zero, return false
   • Build the number: x = x * 10 + int(abbr[j]). This handles multi-digit numbers like converting '1' followed by '0' into 10

   Case 2: Current character in abbr is a letter

   • First, apply any accumulated skip: Move i forward by x positions (i += x)
   • Reset the accumulator: x = 0
   • Validate the match:
     • If i >= m, we've gone beyond the word's length, return false
     • If word[i] != abbr[j], characters don't match, return false
   • If valid, move to next character in word: i += 1

   After processing either case, advance in abbreviation: j += 1

3. Final validation: After the loop ends, check if both strings are fully consumed:

   • i + x == m: The word pointer plus any remaining skip should equal word length
   • j == n: The abbreviation should be fully processed
   • Return true only if both conditions are met

Example walkthrough with word = "substitution", abbr = "s10n":

• Start: i=0, j=0, x=0
• abbr[0]='s' (letter): Skip by x=0, check word[0]='s' matches, move i=1, j=1
• abbr[1]='1' (digit): Build x=1, move j=2
• abbr[2]='0' (digit): Build x=10, move j=3
• abbr[3]='n' (letter): Skip by x=10 making i=11, check word[11]='n' matches, move i=12, j=4
• End: i+x=12+0=12 equals m=12, and j=4 equals n=4, return true

This approach efficiently handles all validation rules in a single pass with O(n) time complexity and O(1) space complexity.

Example Walkthrough

Let's walk through a detailed example with word = "internationalization" and abbr = "i12iz4n".

Initial Setup:

• word = "internationalization" (length 20)
• abbr = "i12iz4n" (length 7)
• i = 0, j = 0, x = 0

Step 1: j=0, abbr[0]='i' (letter)

• Apply skip: i = 0 + 0 = 0
• Reset: x = 0
• Check match: word[0]='i' vs abbr[0]='i' ✓
• Advance: i = 1, j = 1

Step 2: j=1, abbr[1]='1' (digit)

• Not leading zero (x=0 but digit='1')
• Build number: x = 0 * 10 + 1 = 1
• Advance: j = 2

Step 3: j=2, abbr[2]='2' (digit)

• Continue building: x = 1 * 10 + 2 = 12
• Advance: j = 3

Step 4: j=3, abbr[3]='i' (letter)

• Apply skip: i = 1 + 12 = 13
• Reset: x = 0
• Check match: word[13]='i' vs abbr[3]='i' ✓
• Advance: i = 14, j = 4

Step 5: j=4, abbr[4]='z' (letter)

• Apply skip: i = 14 + 0 = 14
• Reset: x = 0
• Check match: word[14]='z' vs abbr[4]='z' ✓
• Advance: i = 15, j = 5

Step 6: j=5, abbr[5]='4' (digit)

• Build number: x = 0 * 10 + 4 = 4
• Advance: j = 6

Step 7: j=6, abbr[6]='n' (letter)

• Apply skip: i = 15 + 4 = 19
• Reset: x = 0
• Check match: word[19]='n' vs abbr[6]='n' ✓
• Advance: i = 20, j = 7

Final Check:

• i + x = 20 + 0 = 20 equals word length ✓
• j = 7 equals abbr length ✓
• Return true

The abbreviation is valid! It represents: keep 'i', skip 12 characters ("nternational"), keep 'iz', skip 4 characters ("atio"), keep 'n'.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m + n), where m is the length of the string word and n is the length of the string abbr.

The algorithm uses two pointers i and j to traverse through word and abbr respectively. In the while loop:

• Pointer j traverses through each character in abbr exactly once, contributing O(n) operations
• Pointer i advances through word either character by character or by jumping forward when processing digits in the abbreviation
• In the worst case, i traverses through all characters in word, contributing O(m) operations
• Each iteration performs constant time operations (digit checking, character comparison, arithmetic operations)

Since both strings are traversed at most once, the total time complexity is O(m + n).

Space Complexity: O(1)

The algorithm only uses a fixed number of variables:

• Three integer variables: i, j, and x for tracking positions and accumulating digit values
• Two integer variables: m and n for storing string lengths

No additional data structures are created that scale with the input size. All operations are performed in-place using constant extra space, resulting in O(1) space complexity.

Common Pitfalls

1. Forgetting to Apply Remaining Skip Count in Final Validation

The Pitfall: A common mistake is checking only word_index == word_length at the end, forgetting that there might be a remaining skip count that hasn't been applied yet. For example, with word = "hi" and abbr = "h1", after processing 'h', we have word_index = 1 and skip_count = 1. If we only check word_index == word_length, we'd incorrectly return False.

Incorrect Final Check:

# Wrong - doesn't account for remaining skip_count
return word_index == word_length and abbr_index == abbr_length

Correct Solution:

# Correct - adds remaining skip_count to word_index
return word_index + skip_count == word_length and abbr_index == abbr_length

2. Mishandling Leading Zeros Detection

The Pitfall: Simply checking if abbr[abbr_index] == '0' is insufficient. We need to ensure it's a leading zero (start of a number), not a valid zero in a multi-digit number like "10".

Incorrect Check:

if current_abbr_char == '0':  # Wrong - rejects valid numbers like "10"
    return False

Correct Solution:

if current_abbr_char == '0' and skip_count == 0:  # Only reject if it's a leading zero
    return False

3. Processing Letters Before Applying Skip Count

The Pitfall: When encountering a letter in the abbreviation, forgetting to first apply any accumulated skip count before comparing characters leads to incorrect position matching.

Incorrect Order:

else:  # Letter case
    # Wrong - comparing before skipping
    if word[word_index] != current_abbr_char:
        return False
    word_index += skip_count  # Applied too late

Correct Solution:

else:  # Letter case
    # First apply the skip
    word_index += skip_count
    skip_count = 0
  
    # Then validate bounds and character match
    if word_index >= word_length or word[word_index] != current_abbr_char:
        return False

4. Not Resetting Skip Count After Use

The Pitfall: After applying a skip count when encountering a letter, failing to reset it to 0 causes the same skip to be incorrectly applied multiple times.

Missing Reset:

else:
    word_index += skip_count
    # Forgot: skip_count = 0
    if word_index >= word_length or word[word_index] != current_abbr_char:
        return False

Correct Solution: Always reset skip_count = 0 immediately after using it to prevent reuse.