408. Valid Word Abbreviation

408

EasyTwo PointersTwo pointers (string matching)Parallel pointers parsing numeric skips

Valid Word Abbreviation

A string can be abbreviated by replacing any number of non-adjacent, non-empty substrings with their lengths (the replaced substrings must not be adjacent). Given a full word and an abbreviation abbr, return true if abbr is a valid abbreviation of word. Numbers in abbr must not contain leading zeros.

Open official problem prompt ↗

In plain English

Verify that an abbreviation, where numbers stand for counts of skipped letters, exactly reconstructs the given word.

Picture it like this

Following shorthand directions where a number means 'walk past that many houses': you and the map must arrive at the same address, and a note like '05' (a leading zero) is nonsense and disqualifies the route.

Example

Input: word = "internationalization", abbr = "i12iz4n"
Output: true
Why: i + (skip 12) + iz + (skip 4) + n reconstructs 'i' + 'nternationaliz'... exactly matching all 20 letters of the word.

Constraints

1 <= word.length <= 20word consists of only lowercase English letters1 <= abbr.length <= 10abbr consists of lowercase English letters and digits

Pattern lesson

See the pattern, then code

Parallel pointers parsing numeric skips

↗

Two Pointers

Sorted input, opposite-end scanning, pair search, or in-place compaction.. Keep one pointer in word and one in abbr; letters must match one-for-one, while a digit run in abbr tells you how many characters of word to skip, with a leading zero being illegal.

New words, made simpleKnow these before the algorithm

Abbreviation: The word with some substrings replaced by the count of characters they covered.
Leading zero: A number written starting with 0, which is invalid here because a skip count is never zero-padded.
Parallel pointers: Two indices advancing through two strings in lockstep according to matching rules.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Expand the abbreviation

Works but builds an intermediate string and complicates leading-zero handling.

Reconstruct the full string from abbr by inserting placeholder characters for each numeric skip, then compare lengths and letters.

Time O(n)Space O(n)

Best choiceTwo-pointer parse

Constant space, single pass, and rejects malformed numbers as it reads them.

Walk word and abbr together, matching letters directly and jumping the word pointer by each parsed number.

Time O(n)Space O(1)

The rule we keep true

Invariant

The prefix word[0:i] is exactly explained by the prefix abbr[0:j] — every letter matched and every skip accounted for.

Why this is correct

Reasoning

Each abbr character is consumed exactly once: a letter must equal the aligned word letter, and a digit run advances i by a precise count. A skip that runs past the end of word leaves i > len(word), and any unmatched trailing letters leave the two pointers unequal at their ends, so the final equality check catches every form of mismatch. Rejecting a leading zero enforces the unique-number rule.

The algorithm in three movesSay these aloud before coding

1Set i = 0 in word and j = 0 in abbr

match 'i', i=1 j=1

2If abbr[j] is a digit, reject a leading zero, else parse the full number and add it to i

parse '12' -> i=13, j=3

3If abbr[j] is a letter, it must equal word[i]; advance both

match 'i','z', parse '4' -> i=19, match 'n' -> i=20

4Continue until either string is exhausted

i==20 and j==7 -> true

5Return true only if both i and j reached their ends together

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readword[0]='i', abbr[0]='i'

2 · AskLetters equal?

3 · Update statei=0 j=0

4 · ResultMatch, i=1 j=1

Key takeaway

The digit run '12' in abbr (indices 1-2) advances the word pointer by twelve characters.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Initialize both pointers
i tracks the word, j tracks the abbreviation, both from the start.
2
Lines 4Loop while both have characters
Parsing stops as soon as either string is consumed.
3
Lines 5-6Reject leading zeros
A digit run beginning with '0' is an invalid count and immediately fails.
4
Lines 7-10Parse the full number and skip
Accumulate consecutive digits into num, then jump the word pointer forward by that many characters.
5
Lines 11-14Match a literal letter
A non-digit must equal the current word letter; otherwise the abbreviation is wrong.
6
Lines 15Require both to finish together
Only if i and j both reached their ends does abbr fully and exactly describe word.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A number that skips past the end of word, e.g. word='a', abbr='2'
Leading zero such as abbr='01'
abbr identical to word (no numbers)
A trailing number that lands exactly on len(word)
Extra unmatched letters left in either string

Common beginner mistakes

Only comparing consumed lengths and forgetting the final j == len(abbr) check, accepting leftover abbr characters
Parsing a single digit at a time instead of the whole multi-digit number
Allowing '0' as a valid skip count
Letting the word pointer overrun the array without a final bounds check

Check your understanding

Why is the final check i == len(word) and j == len(abbr) both required rather than just one?

PyPython 3 · solution.py

Optimal

1class Solution:2    def validWordAbbreviation(self, word: str, abbr: str) -> bool:3        i = j = 04        while i < len(word) and j < len(abbr):5            if abbr[j].isdigit():6                if abbr[j] == '0':7                    return False8                num = 09                while j < len(abbr) and abbr[j].isdigit():10                    num = num * 10 + int(abbr[j])11                    j += 112                i += num13            else:14                if word[i] != abbr[j]:15                    return False16                i += 117                j += 118        return i == len(word) and j == len(abbr)

Time complexityO(n)Optimized

Space complexityO(1)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

MetaGoogleAmazon

Valid Word Abbreviation

Valid Word Abbreviation

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Two Pointers