难度: Easy
Submission
运行时间: 20 ms
内存: 16.6 MB
class Solution:
def validWordAbbreviation(self, word: str, abbr: str) -> bool:
i, j, num = 0, 0, 0
while i < len(word) and j < len(abbr):
if abbr[j].isdigit():
if abbr[j] == "0" and num == 0: # 缩写中的数字不能有前导零
return False
num = num * 10 + int(abbr[j])
j += 1
else:
i += num
num = 0
if i >= len(word) or word[i] != abbr[j]:
return False
i += 1
j += 1
return i + num == len(word) and j == len(abbr)
Explain
这个题解使用双指针 i 和 j 分别指向原单词 word 和缩写 abbr，同时用变量 num 记录缩写中的数字。遍历 abbr，如果遇到数字，则更新 num；如果遇到字母，则将 i 向后移动 num 个位置，num 重置为0，并比较 word[i] 和 abbr[j] 是否相等。最后判断 i+num 是否等于 word 的长度并且 j 是否等于 abbr 的长度，若相等则说明缩写与原单词匹配。
时间复杂度: O(n+m)
空间复杂度: O(1)
class Solution:
def validWordAbbreviation(self, word: str, abbr: str) -> bool:
i, j, num = 0, 0, 0
while i < len(word) and j < len(abbr):
if abbr[j].isdigit():
if abbr[j] == "0" and num == 0: # 缩写中的数字不能有前导零
return False
num = num * 10 + int(abbr[j]) # 更新数字 num
j += 1
else:
i += num # 将 i 向后移动 num 个位置
num = 0 # num 重置为 0
if i >= len(word) or word[i] != abbr[j]: # 比较 word[i] 和 abbr[j]
return False
i += 1
j += 1
return i + num == len(word) and j == len(abbr) # 判断缩写与原单词是否完全匹配
Explore
在题解中，数字的连续读取是通过一个循环实现的，每当遇到数字字符时，会将其转换为整数并累加到当前的数字变量 `num` 中，具体方法是将 `num` 乘以 10 然后加上新的数字，这样可以正确地从字符形式的数字构建整数。为了防止处理中出现前导零的情况，我们检查如果数字的第一个字符是 '0' 且 `num` 为 0（即这是一个新的数字开始），则直接返回 `False`，因为这种情况表示数字有不合法的前导零。
这种处理方式是因为缩写 abbr 中的数字表示原单词 word 中相应位置跳过的字符数。因此，当遇到字母时，我们需要根据之前累积的数字 `num`（表示跳过的字符数量），首先将 `i` 指针向前移动 `num` 个位置，以对齐到正确的比较位置。然后，`num` 被重置为 0，以便处理后续的数字。如果直接比较而不移动 `i`，则会导致比较的位置不正确，因而无法正确验证缩写和原单词是否匹配。
此检查确保所有字符和跳过的位置都已经完全匹配处理完毕。`i + num == len(word)` 确保 `i` 指针加上最后一个数字（如果有）正好可以走到 word 的末尾，即所有字符都被正确考虑且无多余字符。`j == len(abbr)` 确保 `j` 指针走到了 abbr 的末尾，即缩写中的每个字符和数字都被处理。只有这两个条件同时满足时，才能确认缩写完全符合原单词。
在解决方案中，如果 `abbr` 中的数字表示的跳过字符数超过了 `word` 的长度，那么在处理过程中，`i` 指针会超出 `word` 的长度范围。这将在比较 `word[i]` 和 `abbr[j]` 或在最终的检查 `i + num == len(word)` 时被捕获。如果 `i` 指针在任何时候超出 `word` 的长度，算法会返回 `False`，表示缩写不匹配原单词。