Check Whether a Letters-and-Numbers Abbreviation Matches a Word

A word can be abbreviated by replacing some of its non-empty substrings with their lengths, written in decimal. For example, "abbreviation" can be written as "a10n", "ab3v2t1on" or "12".

Given a string word and a string abbr, return whether abbr is a valid abbreviation of word.

Function Signature

def is_valid_abbreviation(word: str, abbr: str) -> bool:

Rules

• Read abbr from left to right. A letter must equal the next unmatched character of word. A maximal run of consecutive digits is read as one decimal number k, and it skips the next k characters of word.
• A digit run that starts with 0 is invalid, so runs such as "0" or "05" never appear in a valid abbreviation. Every skip is therefore at least 1 character.
• abbr is valid exactly when the end of abbr and the end of word are reached at the same time. A skip that would go past the end of word makes abbr invalid, and so does reaching the end of abbr while characters of word remain.
• Letters are compared exactly.

Constraints

• 1 <= len(word) <= 10^5, and word consists of lowercase English letters.
• 1 <= len(abbr) <= 10^5, and abbr consists of lowercase English letters and the digits 0 to 9.
• Every maximal run of digits in abbr has at most 9 digits, so every skip count is below 10^9 and fits in a 32-bit signed integer.

Examples

Example 1

Input:  word = "abbreviation", abbr = "ab3v2t1on"
Output: True

"ab" matches, 3 skips "bre", "v" matches, 2 skips "ia", "t" matches, 1 skips "i", and "on" matches. Both strings end together.

Example 2

Input:  word = "substitution", abbr = "s010n"
Output: False

The digit run "010" starts with 0.

Example 3

Input:  word = "apple", abbr = "a2e"
Output: False

After "a" matches and 2 skips "pp", the next character of word is "l", which does not equal "e".

Check a Numeric Word Abbreviation

Hints

1. Process abbr from left to right and keep track of how many characters of word have been accounted for so far.
2. A run of several digits is one number, and the first digit of a run already tells you whether the run can be valid.
3. The answer depends on both strings running out at exactly the same moment, so think about what happens when abbr would move past the end of word or stop before it.

Approach

Scan abbr once from left to right with two indices: j over abbr, and i, the number of characters of word already matched or skipped (m = len(abbr), n = len(word)). If abbr[j] is a letter, word must still have a character at position i and it must equal abbr[j] exactly; then both indices advance. If abbr[j] is a digit, it is the first digit of a maximal digit run: when that first digit is '0' the run has a leading zero and the answer is False; otherwise the whole run is read as one decimal number k and i advances by k, returning False as soon as i exceeds n (the skip would go past the end of word). Invariant: after each step, abbr[0:j] is a valid abbreviation of exactly word[0:i]. Each letter can only correspond to word[i] and each run consumes exactly k characters, so no choice is ever involved; abbr is valid exactly when the scan consumes all of abbr without failing and finishes with i == n, which is the rule that both strings end at the same time. Edge cases: a letter that appears after word is exhausted, a skip that overshoots the end, abbr ending while characters of word remain, runs such as '0' or '05' at the start, middle or end of abbr, and multi-digit runs that must be read as one number rather than digit by digit. Every skip is below 10^9 and i is at most 10^5 before a skip, so i stays below 10^9 + 10^5 and never exceeds 2^31 - 1.

• Time complexity: O(m)
• Space complexity: O(1)