Problem statement

https://leetcode.com/problems/expressive-words/

Solution

What we need to do is group symbols in groups, using for example groupby. Then we iterate over words and for each word we check first if lengths are the same, and then go symbol by symbol: if they are not equal, return False immediately. If symbols are equal, but length in word is more than in S we also return False. Finally, if length is less, but they are equal to 1 and 2, we also return False, because group should have size 3 or more. If everything passed, we return True.

Complexity

Time complexity is O(S1 + S2 + ... + Sn + T), where S1, ..., Sn are lengths of word in words, T is length of S; space complexity is O(max Si + T).

Code

class Solution:
    def expressiveWords(self, S, words):
        def group(s): 
            return [(i, len(list(j))) for i, j in groupby(s)] 

        def check(gr1, gr2):
            if len(gr1) != len(gr2): return False
            for (i1, i2), (j1, j2) in zip(gr1, gr2):
                if i1 != j1: return False
                if i2 < j2 or i2 == 2 and j2 == 1: return False
            return True

        s_group = group(S)
        return sum(check(s_group, group(word)) for word in words)