宁波制作网站软件,中国万网域名注册官网,seo产品推广,哪个网站做线路攻略做得好1967. 作为子字符串出现在单词中的字符串数目
给你一个字符串数组 patterns 和一个字符串 word #xff0c;统计 patterns 中有多少个字符串是 word 的子字符串。返回字符串数目。
子字符串 是字符串中的一个连续字符序列。 示例 1#xff1a;输入#xff1a;patterns [统计 patterns 中有多少个字符串是 word 的子字符串。返回字符串数目。
子字符串 是字符串中的一个连续字符序列。 示例 1输入patterns [a,abc,bc,d], word abc
输出3
解释
- a 是 abc 的子字符串。
- abc 是 abc 的子字符串。
- bc 是 abc 的子字符串。
- d 不是 abc 的子字符串。
patterns 中有 3 个字符串作为子字符串出现在 word 中。示例 2输入patterns [a,b,c], word aaaaabbbbb
输出2
解释
- a 是 aaaaabbbbb 的子字符串。
- b 是 aaaaabbbbb 的子字符串。
- c 不是 aaaaabbbbb 的字符串。
patterns 中有 2 个字符串作为子字符串出现在 word 中。示例 3输入patterns [a,a,a], word ab
输出3
解释patterns 中的每个字符串都作为子字符串出现在 word ab 中。提示
1 patterns.length 1001 patterns[i].length 1001 word.length 100patterns[i] 和 word 由小写英文字母组成
解题思路
使用朴素的解法枚举word中每个字符作为子字符串的开头逐一匹配patterns中的字符串如果匹配成功则结果加一。使用bool类型的数组记录下patterns中对应下标的元素是否已经成功匹配过如果某个pattern已经成功匹配了就不需要后续再进行匹配了
代码
class Solution {
public:int numOfStrings(vectorstring patterns, string word) {int cnt(0);vectorbool check(patterns.size());for (int i 0; i word.size(); i) {for(int j0;jpatterns.size();j){if (check[j]) continue;if (word.substr(i,patterns[j].size())patterns[j]){check[j] true;cnt;} }}return cnt;}
};时间复杂度O(n×∑imi)O(n \times \sum_i m_i)O(n×∑imi)其中 n 为字符串 word\textit{word}word 的长度mim_imi为字符串 patterns[i]\textit{patterns}[i]patterns[i] 的长度。 对于 patterns\textit{patterns}patterns中的每个字符串$ \textit{patterns}[i]$暴力匹配判断是否为 word\textit{word}word子串的时间复杂度为$ O(n \times m_i)$
空间复杂度O(1)
