Solution Explanation: Valid Word Abbreviation

This problem asks whether a given abbreviation abbr is a valid abbreviation of a word word. A valid abbreviation replaces one or more consecutive characters with their count, but these replacements cannot be adjacent.

Approach: Two Pointers and Simulation

The most efficient approach uses two pointers, one for word and one for abbr, to simulate the abbreviation process. We also use a variable to track the numerical part of the abbreviation.

Algorithm:

1. Initialization:

   • i: Pointer for word (starts at 0).
   • j: Pointer for abbr (starts at 0).
   • num: Variable to store the numerical part of the abbreviation (starts at 0).

2. Iteration: The algorithm iterates through abbr.

   • Digit Encountered: If abbr[j] is a digit:
     • If it's '0' and num is 0 (leading zero), the abbreviation is invalid; return false.
     • Otherwise, update num by multiplying by 10 and adding the digit.
   • Character Encountered: If abbr[j] is a character:
     • Advance i by num positions. This simulates skipping the characters replaced by the numerical part of the abbreviation.
     • Reset num to 0.
     • If i is out of bounds or word[i] doesn't match abbr[j], the abbreviation is invalid; return false.
     • Increment i to move to the next character in word.
   • Increment j: Move to the next character in abbr.

3. Final Check: After the loop, if i + num equals the length of word and j equals the length of abbr, the abbreviation is valid; return true. Otherwise, return false.

Time and Space Complexity

• Time Complexity: O(m + n), where m is the length of word and n is the length of abbr. The algorithm iterates through both strings at most once.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space.

Code Implementation (Python)

class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        i, j = 0, 0  # Pointers for word and abbr
        num = 0       # Number in abbreviation
 
        while i < len(word) and j < len(abbr):
            if abbr[j].isdigit():
                if abbr[j] == '0' and num == 0:  # Check for leading zero
                    return False
                num = num * 10 + int(abbr[j])
            else:
                i += num   # Skip characters in word
                num = 0
                if i >= len(word) or word[i] != abbr[j]:
                    return False
                i += 1  # Move to next character in word
            j += 1  # Move to next character in abbr
 
        return i + num == len(word) and j == len(abbr)
 

The code implementations in other languages (Java, C++, Go, TypeScript) follow a similar structure, adapting syntax and data types as needed. The core logic remains consistent across all languages.