题目重点:逐段匹配字母和跳过长度,校验整词覆盖、越界及前导零。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- 练习约定word为ASCII小写字母,abbr由小写字母和十进制数字段组成;数字代表连续跳过的字符数,必须为正且不能有前导零。实际给出的字符集和大小写规则需先确认。
- 必须同时消费完整单词与完整缩写;空单词和空缩写相配,非空单词与空缩写不相配。数字段不能被拆成多个独立跳过操作。
解题路线
- i指向word下一待匹配字符,j指向abbr下一段。字母要求word[i]同字符,并共同前进;数字则连续解析整个数字段,再让i前进skip。
- 循环不变式:word[0:i]恰好被abbr[0:j]完整描述,且0≤i≤len(word)。每次文字匹配或合法跳过保持不变式;终止时i等于词长才是完整匹配。
- 遇到数字段首字符0立即拒绝,所以a01和a0不能悄悄解释为合法空跳过。解析每位后检查skip是否超过剩余词长,避免超长数字被解析成巨大整数。
- 例子先覆盖字母不一致、最后仍剩字符、跳过越界和数字恰好到末尾。写成正则表达式时必须处理转义和输入长度,双指针更直接呈现合同。
手动走一遍
internationalization与i18n匹配:i后跳过18字符,最后匹配n;apple与a3e匹配,与a2e不匹配。word=a时1合法,01与2非法。空/空合法。
Python 参考实现
下面的代码按上文假设实现,适合本地运行并追加自己的测试用例。
代码区可横向滚动;使用键盘时,先聚焦代码区再按方向键查看。
def valid_abbreviation(word,abbr):
"""ASCII lowercase word/literals, positive decimal skips, no leading zero.
Literal matching case sensitive, full consumption required; empty/empty true.
"""
if any(not 'a'<=ch<='z' for ch in word):raise ValueError('lowercase word')
i=j=0
while j<len(abbr):
ch=abbr[j]
if '0'<=ch<='9':
if ch=='0':return False
skip=0
while j<len(abbr) and '0'<=abbr[j]<='9':
skip=skip*10+ord(abbr[j])-ord('0');j+=1
if skip>len(word)-i:return False
i+=skip
else:
if not 'a'<=ch<='z' or i>=len(word) or word[i]!=ch:return False
i+=1;j+=1
return i==len(word)
复杂度
O(W+A)上界时间,包括word字符校验;O(1)个指针和累计器,累计器被剩余词长约束,位空间O(log(W+1))。输入和返回布尔值之外不构造展开字符串。
易错点与追问
容易失分的边界
- 把多位数字逐位跳过,或允许前导零。
- 只看缩写结束,忘记单词是否还剩字符。
- 使用isdigit扩大为Unicode数字却仍按ASCII码转换。
继续深挖
- 若支持Unicode,跳过单位是码点还是用户看到的字素?
- 若允许转义数字字面量,先定义token语法再扩展扫描器。
