Valid Word Abbreviation

408.Valid Word Abbreviation

String

Two Pointers

Problem Statement:

Given a string word and an abbreviation abbr, return whether the string matches with the given abbreviation. A string such as "word" contains only the following valid abbreviations: ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"].

Example:

Input:

word = "internationalization", abbr = "i12iz4n"

→

Output:

true

Algorithm:

1. Use two pointers for word and abbreviation
2. Handle digits by building complete number
3. Handle characters by direct comparison
4. Check final pointer positions match

Complexity:

Time: O(n) | Space: O(1)

Java 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 (k >= word.length()) 
            return false;  // Went beyond word length

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

    return k == word.length();  // Check both strings are fully consumed
}

Python Solution:

def validWordAbbreviation(self, word: str, abbr: str) -> bool:
    k = i = 0  # Pointers for word and abbr
    
    while i < len(abbr):
        if k >= len(word):
            return False
            
        if abbr[i].isdigit():
            if abbr[i] == '0':  # Check leading zero
                return False
                
            num = 0
            while i < len(abbr) and abbr[i].isdigit():
                num = num * 10 + int(abbr[i])
                i += 1
            k += num
        else:
            if k >= len(word) or abbr[i] != word[k]:
                return False
            k += 1
            i += 1
            
    return k == len(word)

C++ Solution:

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