809.md

Expressive Words

Description

link

---

Solution

• See Code

---

Code

O(n)

class Solution:
    '''
    思路：
        1. 用双指针进行移动判断
        2. If S[i] == W[j, i++, j++
        3. If S[i - 2] == S[i - 1] == S[i] or S[i - 1] == S[i] == S[i + 1], i++ 保证连续字符数字大于3就可以靠复制完成要求
        4. return false
    '''
    def expressiveWords(self, S: str, words: List[str]) -> int:
        return sum(self.check(S, W) for W in words)

    def check(self, S, W):
        i, j, n, m = 0, 0, len(S), len(W)
        for i in range(n):
            if j < m and S[i] == W[j]: j += 1
            elif S[i - 1:i + 2] != S[i] * 3 != S[i - 2:i + 1]: return False
        return j == m