发表于 2024.05.09

• 使用数组记录单词中连续字符的个数，然后再两两比对，不能扩展的情况有以下四种：1. word中出现了s中没有出现的字符；2. word中不连续字符个数和s不相等(如sass和sa)；3. s中某个字符连续次数不超过3, 但word中该位置的字符连续次数又不相等(如sass和sas)；4. word中某个位置的字符连续次数超过了s相应位置字符的次数(没办法缩)。

  class Solution:
      def expressiveWords(self, s: str, words: List[str]) -> int:
          # 统计字符串中连续字符的信息, (字符, 连续个数)
          s_char_info = []  # type: List[List[int]]
          s_ch_set = set(s)
  
          for ch in s:
              if not s_char_info or s_char_info[-1][0] != ch:
                  s_char_info.append([ch, 0])
              s_char_info[-1][1] += 1
  
          ans = 0
          for word in words:
              word_char_info = []  # type: List[List[int]]
              ok = True
              for ch in word:
                  if ch not in s_ch_set:  # 如果出现s中不存在的字符, 提前终止
                      ok = False
                      break
                  # 同理, 连续统计
                  if not word_char_info or word_char_info[-1][0] != ch:
                      word_char_info.append([ch, 0])
                  word_char_info[-1][1] += 1
  
              # 如果出现s不存在的字符(ok=False) 或者 不连续字符数不匹配(如 sasss和sa)
              if not ok or len(s_char_info) != len(word_char_info):
                  continue
  
              for i in range(len(s_char_info)):
                  # 不可扩展的情况：
                  # s中某个字符连续次数不超过3, 但word中该位置的字符连续次数又不相等
                  # word中某个位置的字符连续次数超过了s相应位置字符的次数(没办法缩)
                  if (s_char_info[i][1] < 3 and s_char_info[i][1] != word_char_info[i][1] or
                          s_char_info[i][1] < word_char_info[i][1]):
                      ok = False
                      break
              if ok:
                  ans += 1
          return ans

• LC 题目链接