Code Implementation

class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        i = 0  # pointer for word
        j = 0  # pointer for abbr

        while i < len(word) and j < len(abbr):
            if abbr[j].isdigit():
                if abbr[j] == '0':
                    return False  # leading zeros not allowed
                num = 0
                while j < len(abbr) and abbr[j].isdigit():
                    num = num * 10 + int(abbr[j])
                    j += 1
                i += num
            else:
                if word[i] != abbr[j]:
                    return False
                i += 1
                j += 1
        return i == len(word) and j == len(abbr)
      

class Solution {
public:
    bool validWordAbbreviation(string word, string abbr) {
        int i = 0, j = 0;
        while (i < word.size() && j < abbr.size()) {
            if (isdigit(abbr[j])) {
                if (abbr[j] == '0') return false; // leading zero
                int num = 0;
                while (j < abbr.size() && isdigit(abbr[j])) {
                    num = num * 10 + (abbr[j] - '0');
                    ++j;
                }
                i += num;
            } else {
                if (word[i] != abbr[j]) return false;
                ++i;
                ++j;
            }
        }
        return i == word.size() && j == abbr.size();
    }
};
      

class Solution {
    public boolean validWordAbbreviation(String word, String abbr) {
        int i = 0, j = 0;
        while (i < word.length() && j < abbr.length()) {
            if (Character.isDigit(abbr.charAt(j))) {
                if (abbr.charAt(j) == '0') return false;
                int num = 0;
                while (j < abbr.length() && Character.isDigit(abbr.charAt(j))) {
                    num = num * 10 + (abbr.charAt(j) - '0');
                    j++;
                }
                i += num;
            } else {
                if (word.charAt(i) != abbr.charAt(j)) return false;
                i++;
                j++;
            }
        }
        return i == word.length() && j == abbr.length();
    }
}
      

var validWordAbbreviation = function(word, abbr) {
    let i = 0, j = 0;
    while (i < word.length && j < abbr.length) {
        if (abbr[j] >= '0' && abbr[j] <= '9') {
            if (abbr[j] === '0') return false;
            let num = 0;
            while (j < abbr.length && abbr[j] >= '0' && abbr[j] <= '9') {
                num = num * 10 + parseInt(abbr[j]);
                j++;
            }
            i += num;
        } else {
            if (word[i] !== abbr[j]) return false;
            i++;
            j++;
        }
    }
    return i === word.length && j === abbr.length;
};
      

Problem Description

Given a non-empty string word and a string abbr that represents an abbreviation, determine if abbr is a valid abbreviation of word.

In an abbreviation, each number represents the number of characters to skip in word. Numbers cannot have leading zeros and must be at least one digit. Characters in abbr that are not digits must match the corresponding character in word.

The task is to check if you can reconstruct word from abbr by following these rules, using each character and number in order, and not skipping or reusing any character in word or abbr.

Thought Process

The main challenge is to interpret the abbreviation correctly: when you see a digit, you must skip that many characters in the original word. If you see a letter, it must match the corresponding letter in the word.

A brute-force approach would be to reconstruct the abbreviation into a string and compare it to word, but this is inefficient and unnecessary. Instead, we can use two pointers: one for word and one for abbr. As we process each character in abbr, we move the pointer in word accordingly.

We must also handle edge cases, such as leading zeros in numbers (which are not allowed), and ensure that we do not run past the end of either string.

Solution Approach

• Use Two Pointers: One pointer (i) tracks the position in word, and the other pointer (j) tracks the position in abbr.
• Iterate through abbr: For each character in abbr:
  • If it's a digit, read the full number (could be multiple digits), making sure it does not start with '0'. This number tells you how many characters to skip in word. Move the word pointer forward by this number.
  • If it's a letter, check if it matches the current character in word. If it does, move both pointers forward by one. If not, return false.
• Finish Both Strings: At the end, both pointers should be at the end of their respective strings. If not, the abbreviation is invalid.
• Edge Cases: If there's a leading zero in a number, return false immediately. If you try to skip more characters than are left in word, return false.

Example Walkthrough

Let's take word = "internationalization" and abbr = "i12iz4n".

• Start with i = 0 (word), j = 0 (abbr).
• abbr[0] = 'i': matches word[0] = 'i'. Increment both pointers.
• abbr[1] = '1': start reading number. abbr[1:3] = "12", so skip 12 characters in word. i = 1 + 12 = 13, j = 3.
• abbr[3] = 'i': matches word[13] = 'i'. Increment both pointers.
• abbr[4] = 'z': matches word[14] = 'z'. Increment both pointers.
• abbr[5] = '4': read number, skip 4 characters. i = 15 + 4 = 19, j = 6.
• abbr[6] = 'n': matches word[19] = 'n'. Increment both pointers.
• Both pointers are at the end. Return true.

Time and Space Complexity

• Brute-force Approach: Reconstructing the string from the abbreviation and comparing it to word would be O(N) time and O(N) space, where N is the length of word.
• Optimized Approach: Using two pointers, we scan through both strings once. This is O(M) time, where M is the length of abbr, and O(1) space, since we only use a few variables.

Summary

The key to solving the Valid Word Abbreviation problem efficiently is to process both the word and abbreviation in a single pass using two pointers. By carefully handling digits (for skips) and letters (for direct matches), and watching out for edge cases like leading zeros, we can quickly determine if the abbreviation is valid. This approach is both time and space efficient, and highlights the power of pointer-based string scanning for parsing problems.