LeetCode 408 Valid Word Abbreviation (Python)

Posted by 小明MaxMing on November 3, 2024

题目

A string can be abbreviated by replacing any number of non-adjacent, non-empty substrings with their lengths. The lengths should not have leading zeros.

For example, a string such as “substitution” could be abbreviated as (but not limited to):

“s10n” (“s ubstitutio n”) “sub4u4” (“sub stit u tion”) “12” (“substitution”) “su3i1u2on” (“su bst i t u ti on”) “substitution” (no substrings replaced) The following are not valid abbreviations:

“s55n” (“s ubsti tutio n”, the replaced substrings are adjacent) “s010n” (has leading zeros) “s0ubstitution” (replaces an empty substring) Given a string word and an abbreviation abbr, return whether the string matches the given abbreviation.

A substring is a contiguous non-empty sequence of characters within a string.

解题思路

两个指针指向字符串和缩写,同时向右移动,如果缩写是数字,就记录下来记录当前数字,直到不是数字为止,遇到字母,指向单词的指针向右移动数字位置,判断不能越界且对应的字母相等,最后处理缩写尾部是数字的情况,并且两个指针都到走到最后

代码

class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        m, n = len(word), len(abbr)
        i = j = cur = 0
        while i < m and j < n:
            if abbr[j].isdigit():
                if abbr[j] == "0" and cur == 0:
                    return False
                cur = cur * 10 + int(abbr[j])
            else:
                i += cur
                cur = 0
                if i >= m or word[i] != abbr[j]:
                    return False
                i += 1
            j += 1
        return i + cur == m and j == n

视频讲解 YouTube<--欢迎点击订阅

视频讲解 bilibili<--欢迎点击订阅