Valid Word Abbreviation

XXX. Valid Word Abbreviation

String Manipulation

Two Pointer

Problem Statement:

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

A string abbr is valid if it consists of numbers and letters, where the numbers represent the count of characters skipped in word. Any number in abbr must not contain leading zeros.

Algorithm:

The problem can be solved using a two-pointer approach:

1. Use two pointers: one to iterate through word and another to iterate through abbr.
2. For each character in abbr:
   • If it is a digit:
     • Ensure it is not '0' to avoid leading zeros.
     • Build the number and skip that many characters in word.
   • If it is a letter, compare it to the corresponding character in word. If they do not match, return false.
3. After processing, ensure both pointers have reached the end of their respective strings.

Complexity:

Time Complexity: O(n + m), where n is the length of word and m is the length of abbr. Each character is processed once.
Space Complexity: O(1), as no additional data structures are used.

Java Implementation:

public class Solution {
    public boolean validWordAbbreviation(String word, String abbr) {
        int k = 0; // Pointer for word
        int i = 0; // Pointer for abbr

        while (i < abbr.length()) {
            char curr = abbr.charAt(i);

            // If pointer in word exceeds its length, return false
            if (k >= word.length()) 
                return false;

            if (Character.isDigit(curr)) {
                // Leading zero check
                if (curr == '0') return false;

                // Build the number value
                int num = 0;
                while (i < abbr.length() && Character.isDigit(abbr.charAt(i))) 
                    num = num * 10 + (abbr.charAt(i++) - '0');
                
                // Move pointer in the word
                k += num;
            } else {
                // Check if characters match
                if (k >= word.length() || curr != word.charAt(k)) 
                    return false;
                k++; // Move pointer in word
                i++; // Move pointer in abbr
            }
        }

        // Ensure both pointers reach the end
        return k == word.length();
    }
}