建站之星收费版,网络传销是否传销,郑州建设网站,优秀设计案例1. 题目链接#xff1a;30. 串联所有单词的子串
2. 题目描述#xff1a; 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。 例如#xff0c;如果 words […1. 题目链接30. 串联所有单词的子串
2. 题目描述 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。 例如如果 words [ab,cd,ef] 那么 abcdef abefcdcdabef cdefabefabcd 和 efcdab 都是串联子串。 acdbef 不是串联子串因为他不是任何 words 排列的连接。 返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。 示例 1 输入s barfoothefoobarman, words [foo,bar]
输出[0,9]
解释因为 words.length 2 同时 words[i].length 3连接的子字符串的长度必须为 6。
子串 barfoo 开始位置是 0。它是 words 中以 [bar,foo] 顺序排列的连接。
子串 foobar 开始位置是 9。它是 words 中以 [foo,bar] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。示例 2 输入s wordgoodgoodgoodbestword, words [word,good,best,word]
输出[]
解释因为 words.length 4 并且 words[i].length 4所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。示例 3 输入s barfoofoobarthefoobarman, words [bar,foo,the]
输出[6,9,12]
解释因为 words.length 3 并且 words[i].length 3所以串联子串的长度必须为 9。
子串 foobarthe 开始位置是 6。它是 words 中以 [foo,bar,the] 顺序排列的连接。
子串 barthefoo 开始位置是 9。它是 words 中以 [bar,the,foo] 顺序排列的连接。
子串 thefoobar 开始位置是 12。它是 words 中以 [the,foo,bar] 顺序排列的连接。提示 1 s.length 1041 words.length 50001 words[i].length 30words[i] 和 s 由小写英文字母组成 3. 算法思路 这段代码使用滑动窗口的思想来解决字符串匹配的问题。给定一个主串s和一个模式串words如果s中存在一个子串该子串包含words中所有单词且顺序一致那么这个子串就是words的一个串联子串。代码的目标是在s中寻找所有的串联子串的起始位置。 首先用一个哈希表hash1来保存模式串words中所有单词的频次。然后遍历字符串s的所有可能起始位置记为x。 接下来构建一个新的哈希表hash2用于维护滑动窗口内的单词频次。滑动窗口的起始位置为x终止位置为y窗口的长度是lenwords中单词长度的总和。每次移动窗口时将窗口右边的单词加入到hash2中并更新对应单词的频次和计数count。如果窗口内的单词频次在hash1中存在且小于等于hash1中的频次则count加1。 如果窗口的长度超过len*mm是words中单词的个数说明窗口左边的单词已经不在窗口范围内需要移出窗口并更新hash2和count。具体操作是将窗口左边的单词移出窗口并更新对应单词的频次和count。 最后当count等于m时将窗口左边的起始位置加入到结果集ret中。 最后返回ret即为所有串联子串的起始位置。 4. C算法代码
class Solution {
public:vectorint findSubstring(string s, vectorstring words) {vectorint ret;unordered_mapstring,int hash1;//保存words里面所有单词的频次for(autos:words)hash1[s];int lenwords[0].size();int mwords.size();for(int i0;ilen;i)//执行len次{unordered_mapstring,inthash2;//维护窗口内单词的频次for(int lefti,righti,count0;rightlens.size();rightlen){//进窗口维护countstring ins.substr(right,len);hash2[in];if(hash1.count(in)hash2[in]hash1[in])count;//判断if(right-left1len*m){//出窗口维护countstring outs.substr(left,len);if(hash1.count(out)hash2[out]hash1[out])count--;hash2[out]--;leftlen;}//更新结果if(countm) ret.push_back(left);}}return ret;}
};
