Check Whether a Letters-and-Numbers Abbreviation Matches a Word
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
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
```python
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**
```text
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**
```text
Input: word = "substitution", abbr = "s010n"
Output: False
```
The digit run `"010"` starts with `0`.
**Example 3**
```text
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"`.
Overview: Decide whether an abbreviation made of lowercase letters and decimal skip counts matches a given word, where each number skips that many characters and any number with a leading zero is invalid. It tests careful string scanning, multi-digit number parsing and end-of-input boundary checks.
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`, implement `is_valid_abbreviation(word, abbr)`, which returns a boolean: `True` if `abbr` is a valid abbreviation of `word`, and `False` otherwise.
### 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.
No value in this problem exceeds `2^31 - 1`: a position in `word` plus one skip stays below `10^9 + 10^5`.
### Example 1
```text
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
```text
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"`.
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
Input: ('abbreviation', 'ab3v2t1on')
Expected Output: True
Explanation: Source Example 1: letters and skips alternate (ab, 3, v, 2, t, 1, on) and both strings end together.
Input: ('substitution', 's010n')
Expected Output: False
Explanation: Source Example 2: the digit run '010' in the middle of abbr starts with 0, so abbr is invalid.
Hints
- Process abbr from left to right and keep track of how many characters of word have been accounted for so far.
- A run of several digits is one number, and the first digit of a run already tells you whether the run can be valid.
- 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.