LeetCode 408: Valid Word Abbreviation

link

Non-numeric portion of abbr must match char-by-char with word. For numeric portion:

  1. No leading zeros.
  2. Remaining length of word must be big enough to skip over.

Time \mathcal{O}(n), space: \mathcal{O}(1).

class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        n = len(word)
        m = len(abbr)
        i, j = 0, 0
        while i < n and j < m:
            # Simpler, non-numeric match
            if not abbr[j].isdigit():
                if word[i] != abbr[j]:
                    return False
                i += 1
                j += 1
                continue
            
            # No leading zeroes
            if abbr[j] == "0":
                return False
            
            # Numeric match
            num = 0
            while j < m and abbr[j].isdigit():
                num = 10 * num + int(abbr[j])
                j += 1
            if n-i < num:
                return False 
            i += num
                
        # Both word and expanded abbr 
        # must have been consumed
        return i == n and j == m

Leave a comment