Python solution with detailed explanation


  • 0
    G

    Solution

    Valid Word Abbreviation https://leetcode.com/problems/valid-word-abbreviation/

    • Initialize i and j to 0.
    • If abbr[j] is an alphabet and equal to word[i], then increment i and j. Otherwise it is an invalid case and return False.
    • If abbr[j] is a digit, then scan left to right to extract the number. Then increment i by the number.
    • The while loop runs as long as i and j are less than N and M. Once it terminates, the valid condition will be i == N and j == M. Otherwise it is invalid.

    Interesting Corner Case
    The algorithm is simple. One corner case missed was:
    "a"
    "01"

                elif abbr[j].isdigit():
                    if abbr[j] == '0':
                        return False
    

    Code

    class Solution(object):
        def extract_number(self, j, abbr, M):
            num = 0
            while j < M and abbr[j].isdigit():
                num, j = num*10 + int(abbr[j]), j+1
            return num, j
        
        def validWordAbbreviation(self, word, abbr):
            """
            :type word: str
            :type abbr: str
            :rtype: bool
            """
            i,j,N, M = 0,0,len(word), len(abbr)
            while i < N and j < M:
                if abbr[j].isalpha() and abbr[j] != word[i]:
                    return False
                elif abbr[j].isalpha() and abbr[j] == word[i]:
                    i,j = i+1,j+1
                elif abbr[j].isdigit():
                    if abbr[j] == '0':
                        return False
                    num, j = self.extract_number(j, abbr, M)
                    i = i+num
            return (i==N and j == M)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.