Expressive Words — LeetCode 809 Python Solution

The problem

Sometimes people repeat letters to represent extra feeling. For example: "hello" -> "heeellooo" "hi" -> "hiiii" In these strings like "heeellooo", we have groups of adjacent letters that are all the same: "h", "eee", "ll", "ooo".

Example

Input

s = "heeellooo", words = ["hello", "hi", "helo"]

Output

1

Explanation

We can extend "e" and "o" in the word "hello" to get "heeellooo".

Python solution

class Solution:
    def expressiveWords(self, s: str, words: List[str]) -> int:
        def check(s, t):
            m, n = len(s), len(t)
            if n > m:
                return False
            i = j = 0
            while i < m and j < n:
                if s[i] != t[j]:
                    return False
                k = i
                while k < m and s[k] == s[i]:
                    k += 1
                c1 = k - i
                i, k = k, j
                while k < n and t[k] == t[j]:
                    k += 1
                c2 = k - j
                j = k
                if c1 < c2 or (c1 < 3 and c1 != c2):
                    return False
            return i == m and j == n

        return sum(check(s, t) for t in words)

Complexity

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 809. Expressive Words is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Two Pointers.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Related problems