Leetcode 809. Expressive Words

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

解析：Version 1，依次按顺序统计s与各个单词的字母个数，如果相同顺序（连续相等字母算顺序中的一位）的字母不相等，则不符合条件，如果s的字母个数小于3且s与单词的字母个数不等，不符合条件，如果s的字母个数大于等于3且小于单词的字母个数，不符合条件，执行到某个字符串结束，如果没都达到最后，则不符合条件，否则满足条件。Version 2只统计s一次，然后再比对。

• Version 1

class Solution:
    def expressiveWords(self, s: str, words: List[str]) -> int:
        count = 0
        n = len(s)
        for word in words:
            if self.check(word, s):
                count += 1
        return count


    def check(self, word, s):
        n = len(s)
        m = len(word)
        if m > n:
            return False
        i = 0
        j = 0
        while i < n and j < m:
            if s[i] != word[j]:
                return False
            t1 = 1
            t2 = 1
            while i < n - 1 and s[i] == s[i+1]:
                t1 += 1
                i += 1
            while j < m - 1 and word[j] == word[j+1]:
                t2 += 1
                j += 1
            if (t1 < 3 and t1 != t2) or t1 < t2:
                return False
            i += 1
            j += 1
        return i == n and j == m

• Version 2

class Solution:
    def expressiveWords(self, s: str, words: List[str]) -> int:
        count = 0
        n = len(s)
        stat = []
        i = 0
        while i < n:
            temp = 1
            while i < n - 1 and s[i] == s[i+1]:
                temp += 1
                i += 1
            stat.append((s[i], temp))
            i += 1
        for word in words:
            m = len(word)
            if m > n:
                continue
            if self.check(word, stat):
                count += 1
        return count


    def check(self, word, stat):
        m = len(word)
        i = 0
        j = 0
        while j < m and i < len(stat):
            if stat[i][0] != word[j]:
                return False
            temp = 1
            while j < m - 1 and word[j] == word[j+1]:
                temp += 1
                j += 1
            if (stat[i][1] < 3 and stat[i][1] != temp) or stat[i][1] < temp:
                return False
            i += 1
            j += 1
        return i == len(stat)

Reference

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