0809. Expressive Words¶
题目信息¶
- 题号:
0809
- 难度:
Medium
- 主题:
字符串、连续字符组、拉伸匹配
- 原题:
- 重点:
只能扩展连续相同字符组,扩展后的组长度必须至少为 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,因此只有一个单词具有拉伸性。