Valid Word Abbreviation - Video Solutions

Problem Overview: Given a word and its abbreviation, determine whether the abbreviation correctly represents the original word. Numbers in the abbreviation represent how many characters are skipped in the word, while letters must match exactly in order.

Approach 1: Expand Abbreviation (String Simulation) (Time: O(n), Space: O(n))

The most straightforward method builds the expanded string represented by the abbreviation. Iterate through the abbreviation: if the current character is a digit, parse the full number and append that many placeholder characters (or skip count tracking). If it is a letter, append it directly. After expansion, compare the constructed string with the original word character by character. This approach is easy to reason about but wastes memory because the expanded string can be as long as the original word. It also performs unnecessary string construction when the goal is only validation.

Approach 2: Two Pointers Simulation (Time: O(n), Space: O(1))

The optimal solution processes both strings in a single pass using two indices. One pointer walks through the word and another through the abbreviation. When the abbreviation contains a letter, it must match the current character in the word, and both pointers move forward. When the abbreviation contains a digit, parse the entire number and advance the word pointer by that amount. Leading zeros are invalid and must be rejected immediately. This approach works because the abbreviation directly encodes how far the pointer should jump in the word. The algorithm only scans each character once and never constructs intermediate strings.

Using two pointers keeps the implementation simple and avoids extra memory allocation. The logic mainly revolves around parsing digits and synchronizing movement between the two indices. Since each character of the abbreviation and word is processed at most once, the runtime remains linear.

Handling numeric parsing correctly is the key detail. When a digit is encountered, repeatedly multiply the current value by 10 and add the new digit until a non-digit appears. This handles multi-digit abbreviations like 12 correctly. After parsing, move the word pointer forward by the parsed number.

The solution is essentially a string parsing simulation problem using techniques common in string processing tasks. Careful boundary checks ensure the pointer never moves beyond the word length.

Recommended for interviews: Interviewers expect the two-pointer simulation. The brute-force expansion approach demonstrates understanding of the abbreviation format, but the O(1) space pointer method shows stronger problem-solving and attention to efficiency. Most candidates who pass interviews implement the linear scan with digit parsing.