SWE · Coding

Meta 单词缩写校验:双指针、数字跳过与前导零

逐段匹配字母和跳过长度,校验整词覆盖、越界及前导零。

题目重点:逐段匹配字母和跳过长度,校验整词覆盖、越界及前导零。

题意与假设

这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。

  • 练习约定word为ASCII小写字母,abbr由小写字母和十进制数字段组成;数字代表连续跳过的字符数,必须为正且不能有前导零。实际给出的字符集和大小写规则需先确认。
  • 必须同时消费完整单词与完整缩写;空单词和空缩写相配,非空单词与空缩写不相配。数字段不能被拆成多个独立跳过操作。

解题路线

  1. i指向word下一待匹配字符,j指向abbr下一段。字母要求word[i]同字符,并共同前进;数字则连续解析整个数字段,再让i前进skip。
  2. 循环不变式:word[0:i]恰好被abbr[0:j]完整描述,且0≤i≤len(word)。每次文字匹配或合法跳过保持不变式;终止时i等于词长才是完整匹配。
  3. 遇到数字段首字符0立即拒绝,所以a01和a0不能悄悄解释为合法空跳过。解析每位后检查skip是否超过剩余词长,避免超长数字被解析成巨大整数。
  4. 例子先覆盖字母不一致、最后仍剩字符、跳过越界和数字恰好到末尾。写成正则表达式时必须处理转义和输入长度,双指针更直接呈现合同。

手动走一遍

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语法再扩展扫描器。
✓已复制微信号!