Problem statement

https://leetcode.com/problems/valid-word-abbreviation/

Solution

Let us use groupby functionality to separate string into digits/letter.

  1. First we check if lenght of reconstructed string is equal to original and if not, return false.
  2. Then we check that no digits parts start with 0.
  3. Finally, we reconstruct string, where we put * to abbreviated symbols and compare string.

Complexity

It is $O(n + m)$, where $m$ and $n$ are lengths of original and abbreviated strings.

Code

class Solution:
    def validWordAbbreviation(self, word, abbr):
        t = [(i, "".join(j)) for i, j in groupby(abbr, key = lambda x:x.isdigit())]
        total_len = sum(int(j) for i,j in t if i) + sum(len(j) for i,j in t if not i)
	if total_len != len(word): return False
        if any(j[0] == "0" for i, j in t if i): return False
                
        cand = ""
        for i, j in t:
            if i: cand += int(j)*"*"
            else: cand += j
        
        return all(i==j or i=="*" for i, j in zip(cand, word))