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".