AlgoMaster Logo

Valid Word Abbreviation

easyFrequency5 min readUpdated June 23, 2026

Understanding the Problem

We're given two strings: the original word and an abbr that may contain a mix of letters and numbers. Each number in the abbreviation represents how many characters from the original word were replaced. Our job is to verify that the abbreviation correctly describes the original word.

Three rules govern what counts as a match:

  • Numbers can be multi-digit. 12 means skip 12 characters, not 1 then 2.
  • Leading zeros are not allowed. A number like 01 is invalid, and so is 0 by itself, since a number replaces a non-empty substring and zero characters is empty.
  • A letter in the abbreviation must match the corresponding character in the word exactly.

Key Constraints:

  • Numbers fit in a 32-bit integer, so parsing a multi-digit count into an int never overflows. We do not need a 64-bit type for the running number.
  • abbr mixes letters and digits, so the parser has to branch on character type and consume a full run of digits at once rather than one digit at a time.
  • The word is at most 20 characters. Any parsed count above 20 pushes the word pointer past the end, which the final bounds check rejects, so an oversized number cannot accidentally pass.

Approach 1: Brute Force (Generate and Compare)

Intuition

Expand the abbreviation back into a full-length string, then compare it with the word.

Each letter in the abbreviation maps to one position in the expanded string. Each number maps to that many placeholder positions, which we represent with a wildcard character that matches anything. Once the abbreviation is fully expanded, two checks decide the answer: the expanded length must equal the word length, and every non-wildcard position must match the word.

Algorithm

  1. Initialize an index j for the abbreviation and a list to build the expanded string.
  2. Walk through the abbreviation character by character:
    • If the character is a letter, append it to the expanded list.
    • If the character is a digit, check for leading zeros (if the digit is '0', return false). Parse the full multi-digit number and append that many wildcard characters.
  3. Compare the expanded string with the word:
    • If lengths differ, return false.
    • For each position, if the expanded character is not a wildcard, it must match the corresponding character in the word.

Example Walkthrough

1Parse abbr: 'i' is a letter, add to expanded
0
i
compare
1
n
2
t
3
e
4
r
5
n
6
a
7
t
8
i
9
o
10
n
11
a
12
l
13
i
14
z
15
a
16
t
17
i
18
o
19
n
1/5

Code

The expanded array is the only reason this uses O(n) space. The next approach removes it by advancing a pointer through the word directly instead of materializing wildcards.

Approach 2: Two Pointers (Optimal)

Intuition

The expansion in Approach 1 is unnecessary because the comparison can happen as we parse. Walk both strings with two pointers: i in the word, j in the abbreviation. A letter at abbr[j] consumes one word character; a number at abbr[j] consumes that many. Decoding and matching happen in the same pass, with no intermediate string.

The logic per step:

  • If abbr[j] is a letter, compare it with word[i]. If they match, advance both pointers. If not, return false.
  • If abbr[j] is a digit, parse the full number (rejecting a leading zero), then advance i by that amount.

When the loop ends, both pointers must sit exactly at the end of their strings.

Algorithm

  1. Initialize two pointers: i = 0 for the word, j = 0 for the abbreviation.
  2. While both pointers are within bounds:
    • If abbr[j] is a digit:
      • If it's '0', return false (leading zero).
      • Parse the complete number by consuming consecutive digits.
      • Advance i by that number.
    • If abbr[j] is a letter:
      • If word[i] != abbr[j], return false.
      • Advance both i and j.
  3. Return true only if both i == word.length and j == abbr.length.

Example Walkthrough

word
1Initialize: i=0, j=0
0
i
i
1
n
2
t
3
e
4
r
5
n
6
a
7
t
8
i
9
o
10
n
11
a
12
l
13
i
14
z
15
a
16
t
17
i
18
o
19
n
abbr
1Initialize: i=0, j=0
0
i
j
1
1
2
2
3
i
4
z
5
4
6
n
1/6

Code