AlgoMaster Logo

Valid Word Abbreviation

Last Updated: March 29, 2026

easy

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.

The tricky parts are:

  • Numbers can be multi-digit (e.g., 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 it would replace zero characters, which isn't meaningful).
  • When we encounter a letter in the abbreviation, it must match the corresponding character in the word exactly.

The key observation is that we need to walk through both strings simultaneously: one pointer for the word and one for the abbreviation. When we hit a letter in the abbreviation, we compare it directly. When we hit a digit, we parse the full number and skip that many characters ahead in the word.

Key Constraints:

  • word.length <= 20 and abbr.length <= 10 → These are very small inputs. Even an O(n * m) approach would be fast. But the problem naturally lends itself to an O(n + m) single-pass solution.
  • abbr consists of lowercase letters and digits → We need to handle both character types while parsing.
  • Numbers fit in a 32-bit integer → The skip count can be up to ~2 billion in theory, but since the word is at most 20 characters, any number greater than 20 would immediately make the abbreviation invalid.

Approach 1: Brute Force (Generate and Compare)

Intuition

The most straightforward way to think about this problem is: what if we expand the abbreviation back into a full-length string and then compare it with the word?

When we see a letter in the abbreviation, we place it directly. When we see a number, we insert that many placeholder characters (like wildcards). Then we check if the expanded result has the same length as the word and if every non-wildcard position matches.

This approach mirrors how you'd manually verify an abbreviation on paper. You'd write out the abbreviation, fill in blanks for the numbers, and see if everything lines up.

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

This approach works correctly but wastes space building an expanded string. What if instead of materializing placeholders, we simply moved a pointer forward in the word by the parsed number?

Approach 2: Two Pointers (Optimal)

Intuition

Instead of expanding the abbreviation into a full string, we can walk through both strings simultaneously using two pointers. One pointer (i) tracks our position in the word, and another pointer (j) tracks our position in the abbreviation.

The logic is simple:

  • If the current abbreviation character is a letter, compare it with the current word character. If they match, advance both pointers. If not, return false.
  • If the current abbreviation character is a digit, parse the full number (watching for leading zeros), then advance the word pointer by that amount.

At the end, both pointers must have reached the end of their respective strings. If one finishes before the other, the abbreviation doesn't describe the word correctly.

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

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
1/6
1Initialize: i=0, j=0
0
i
j
1
1
2
2
3
i
4
z
5
4
6
n
1/6

Code