408. Valid Word Abbreviation

• categories: Code, Interview Question, leetcode, Easy
• source: https://leetcode.com/problems/valid-word-abbreviation/description
• topics: String Manipulation, Two Pointers

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(object):
    def validWordAbbreviation(self, word, abbr):
        """
        :type word: str
        :type abbr: str
        :rtype: bool
        """
        i = 0
        j = 0
        n = len(word)
        m = len(abbr)
        while i < n and j < m:
            if word[i] == abbr[j]:
                i += 1
                j += 1
            elif abbr[j] == '0':
                return False
            elif abbr[j].isdigit():
                k = j
                j += 1
                while j < m and abbr[j].isdigit():
                    j += 1
                shift = int(abbr[k:j])
                i += shift
                if i > n:
                    return False
            else:
                return False
        return i >= n and j >= m