0809. Expressive Words

题目信息

题号:

0809

难度:

Medium

主题:

字符串、连续字符组、拉伸匹配

原题:

LeetCode 0809

重点:

只能扩展连续相同字符组,扩展后的组长度必须至少为 3;字符组顺序和种类不能改变

题目重述

给定目标字符串 s 和字符串数组 words。对某个单词,可以重复执行拉伸操作:选择其中一组连续相同字符,在该组中再插入若干个相同字符,并要求操作后的该组长度至少为 3。

若能通过零次或多次拉伸把一个单词变成 s,则称该单词具有拉伸性。拉伸不能删除字符、改变字符顺序或把不同字符组互相合并。请返回 words 中具有拉伸性的单词数量;数组中的重复单词按各自位置分别计数。

1 <= s.length <= 100,1 <= words.length <= 100,每个单词长度在 [1, 100] 范围内;所有字符串只包含小写英文字母。

自建示例

多个字符组独立判断:

输入:s = "aaabccccd", words = ["abcd","aabcd","aaabccd","aaabbccccd","aaabcccc"]
输出:3
解释:"abcd" 可以把 a 组扩为 3 个、c 组扩为 4 个;"aabcd" 只需继续扩展 a 和 c;"aaabccd" 只需把 c 组从 2 个扩为 4 个,因此前三个单词均可得到 s。"aaabbccccd" 含有两个 b,目标只有一个 b,拉伸不能删除字符;"aaabcccc" 缺少末尾 d,也无法通过扩展补出新字符组。

目标中长度为二的组不能由更短组拉伸得到:

输入:s = "xyy", words = ["xyy","xy","xyyy"]
输出:1
解释:"xyy" 零次操作即可匹配。把 "xy" 中单个 y 扩成两个 y 不合法,因为执行拉伸后该组长度必须至少为 3;"xyyy" 又不能删除多出的 y,因此只有一个单词具有拉伸性。