Valid Word Abbreviation

easy string two pointers

Problem

A non-empty string abbr abbreviates a non-empty word. Return whether abbr is a valid abbreviation of word.

Inputword = "internationalization", abbr = "i12iz4n"

Outputtrue

i + 12 + iz + 4 + n perfectly traverses the word.

word

abbr

def valid_word_abbreviation(word, abbr):
    i = j = 0
    while i < len(word) and j < len(abbr):
        if abbr[j].isdigit():
            if abbr[j] == "0": return False
            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)

function validWordAbbreviation(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 + Number(abbr[j]); j++; }
      i += num;
    } else {
      if (word[i] !== abbr[j]) return false;
      i++; j++;
    }
  }
  return i === word.length && j === abbr.length;
}

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');
                i += num;
            } else {
                if (word.charAt(i) != abbr.charAt(j)) return false;
                i++; j++;
            }
        }
        return i == word.length() && j == abbr.length();
    }
}

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

Explanation

An abbreviation replaces runs of letters with a count, like i12iz4n meaning "i, then skip 12 letters, then iz, then skip 4, then n". We verify it by walking the word and the abbreviation together with two pointers, i for the word and j for the abbreviation.

When abbr[j] is a digit, it tells us how many word characters to jump over. We read the full number (digits can be multi-character like 12) and add it to i. A leading 0 is rejected, because a count like 05 is not allowed.

When abbr[j] is a letter, it must match the current word character exactly; if word[i] != abbr[j] we return false. Otherwise both pointers advance by one.

At the end the abbreviation is valid only if both pointers landed exactly on the end (i == len(word) and j == len(abbr)). That ensures the skips and matches covered the whole word with nothing left over.

Example: word = "internationalization", abbr = "i12iz4n". We match i, skip 12 letters, match i and z, skip 4 more, then match the final n — both pointers reach the end together, so the result is true.

Time: O(|word| + |abbr|) Space: O(1)