1. Valid Word Abbreviation (LeetCode)
Model answer
The task
Check whether an abbreviation describes a given word. Letters must match in order, and each number skips that many characters in the word; a number cannot start with zero.
Key idea
Walk through the word and abbreviation with two pointers. When the abbreviation has a digit, parse the whole number and advance the word pointer by that amount; otherwise, the characters must match.
Approach
- Start both pointers at the beginning of their strings.
- If the next abbreviation character is a letter, require it to match the current word character, then advance both pointers.
- If it is a digit, reject a leading zero, parse all consecutive digits as one skip count, and advance the word pointer.
- Reject if a skip goes beyond the word.
- Return true only if both pointers reach the ends together.
class Solution:
def validWordAbbreviation(self, word: str, abbr: str) -> bool:
word_index = 0
abbr_index = 0
while abbr_index < len(abbr):
if abbr[abbr_index].isdigit():
# Leading zeroes are not valid in a skip count.
if abbr[abbr_index] == "0":
return False
skip = 0
while abbr_index < len(abbr) and abbr[abbr_index].isdigit():
skip = skip * 10 + int(abbr[abbr_index])
abbr_index += 1
word_index += skip
if word_index > len(word):
return False
else:
if word_index >= len(word) or word[word_index] != abbr[abbr_index]:
return False
word_index += 1
abbr_index += 1
return word_index == len(word)
Complexity:
- Time: O(n + m), where
nandmare the lengths of the word and abbreviation. - Space: O(1), using only a few pointer and counter variables.
Common follow-ups
- How would you handle Unicode letters? Use the same pointer logic, with the desired definition of “digit” and “letter.”
- Can the abbreviation be validated without parsing large integers? Yes; cap the skip count once it exceeds the remaining word length.
- What edge cases matter? Empty strings, a skip past the end, unmatched trailing characters, and numbers with leading zeroes.