免费下载建筑图纸的网站,百度app下载安装官方免费下载,宁波建设工程报名网站,企业网站建设哪家正规文章目录1. 题目2. 解题1. 题目
有时候人们会用重复写一些字母来表示额外的感受#xff0c;比如 hello - heeellooo, hi - hiii。 我们将相邻字母都相同的一串字符定义为相同字母组#xff0c;例如#xff1a;比如 hello - heeellooo, hi - hiii。 我们将相邻字母都相同的一串字符定义为相同字母组例如h, eee, ll, ooo。
对于一个给定的字符串 S 如果另一个单词能够通过将一些字母组扩张从而使其和 S 相同我们将这个单词定义为可扩张的stretchy。 扩张操作定义如下选择一个字母组包含字母 c 然后往其中添加相同的字母 c 使其长度达到 3 或以上。
例如以 hello 为例我们可以对字母组 o 扩张得到 hellooo但是无法以同样的方法得到 helloo 因为字母组 oo 长度小于 3。 此外我们可以进行另一种扩张 ll - lllll 以获得 helllllooo。如果 S helllllooo那么查询词 hello 是可扩张的因为可以对它执行这两种扩张操作使得 query hello - hellooo - helllllooo S。
输入一组查询单词输出其中可扩张的单词数量。
示例
输入
S heeellooo
words [hello, hi, helo]
输出1
解释
我们能通过扩张 hello 的 e 和 o 来得到 heeellooo。
我们不能通过扩张 helo 来得到 heeellooo 因为 ll 的长度小于 3 。说明
0 len(S) 100。
0 len(words) 100。
0 len(words[i]) 100。
S 和所有在 words 中的单词都只由小写字母组成。来源力扣LeetCode 链接https://leetcode-cn.com/problems/expressive-words 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
class Solution {
public:int expressiveWords(string S, vectorstring words) {if(S ) return 0;int ans 0, num 0;vectorchar S_char;//记录连续的单一字符vectorint count;//单一字符个数char prev S[0];for(int i 0; i S.size(); i){if(S[i] ! prev){S_char.push_back(prev);count.push_back(num);num 1;prev S[i];}else{num;}}S_char.push_back(prev);count.push_back(num);for(auto w : words){if(w )continue;bool flag true;int i 0;num 0;prev w[0];// 对每个单词同样的方法for(int j 0; j w.size(); j){if(w[j] ! prev){if(i S_char.size() || prev ! S_char[i] || count[i] num|| (count[i] ! num count[i]3)){// 字符跟S不匹配、S的字符数小于num、个数不等且S中的个数小于3flag false;//不能得到Sbreak;}i;num 1;prev w[j];}else{num;}}if(i S_char.size() || prev ! S_char[i] || count[i] num|| (count[i] ! num count[i]3))flag false;if(flag i S_char.size()-1)ans;}return ans;}
};8 ms 7.6 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
