239. Valid Word Abbreviation

Walk both strings together. A digit run in the abbreviation is a skip count over the word; a letter must match the current word character.

Match or skip

Keep pointers i into word and j into abbr:

• If abbr[j] is a digit (no leading zero), read the whole number and advance i by that many characters.
• Otherwise abbr[j] must equal word[i]; advance both.

The abbreviation is valid iff both pointers reach the end together.

while i<len(word) and j<len(abbr):
    if digit: (reject leading 0) read num; i += num
    else: if word[i]!=abbr[j]: return False; i++, j++
return i == len(word) and j == len(abbr)

Worked example

"internationalization", "i12iz4n" → i, skip 12, iz, skip 4, n → true.

Complexity

• Time: O(n).
• Space: O(1).

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;  // no leading zero
                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();
    }
}