408. Valid Word Abbreviation
Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 31.5%
Problem Breakdown
The problem asks us to determine whether a given string s matches an abbreviation abbr. An abbreviation can contain lowercase letters and digits, where digits represent consecutive groups of characters in the original string that are omitted. The task is to verify if the abbreviation correctly represents the original string.
Inputs:
s: A non-empty string containing only lowercase letters.abbr: A string containing only lowercase letters and digits.
Outputs:
- A boolean value indicating whether
abbris a valid abbreviation ofs.
Implicit Constraints or Tricky Edge Cases:
- The abbreviation can start with a digit, which means the original string must have at least that many characters.
- Multiple consecutive digits in the abbreviation are not allowed (e.g., “a12b” is invalid).
- An empty abbreviation is considered valid for any non-empty string.
Intuition
A brute-force approach would involve generating all possible abbreviations of s and checking if abbr matches any of them. However, this approach is impractical due to its exponential time complexity.
The key insight is to use a two-pointer technique to traverse both the original string s and the abbreviation abbr. By carefully handling digits in abbr, we can determine if it correctly represents s.
Approach
- Initialize two pointers,
iforsandjforabbr. - Traverse through both strings:
- If
abbr[j]is a digit, accumulate the number represented by consecutive digits. - Move the pointer
iinsby the accumulated number of characters. - If
abbr[j]is a letter, check if it matchess[i]. If not, returnFalse.
- If
- After processing both strings, ensure that all characters in both have been processed correctly.
Complexity Analysis
- Time Complexity: O(n + m), where n is the length of
sand m is the length ofabbr. We traverse each string once. - Space Complexity: O(1). We use a constant amount of extra space for variables.
Solution
def validWordAbbreviation(s: str, abbr: str) -> bool:
i, j = 0, 0
while i < len(s) and j < len(abbr):
if abbr[j].isdigit():
# Handle multiple digits
if abbr[j] == '0':
return False # Leading zero is invalid
num = 0
while j < len(abbr) and abbr[j].isdigit():
num = num * 10 + int(abbr[j])
j += 1
i += num
else:
if s[i] != abbr[j]:
return False
i += 1
j += 1
# Ensure both strings are fully traversed
return i == len(s) and j == len(abbr)
Edge Cases Handled
- Leading zeros in
abbr: The code returnsFalseif a digit starts with ‘0’. - Empty abbreviation: If
abbris empty, it will not match any non-emptys. - Mismatched lengths after processing: The final check ensures both strings are fully traversed.
- Consecutive digits in
abbr: The code accumulates digits correctly and skips the corresponding number of characters ins.