湖南网站建设公司 找磐石网络一流,南宁网站建设gxskm,好的网站或网页,宁波住房和城乡建设培训网站题目#xff1a; 串联所有单词的子串(1中等)
描述#xff1a;
给定两个字符串 s 和 p#xff0c;找到 s 中所有 p 的 异位词 的子串#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串#xff08;包括相同的字符串 串联所有单词的子串(1中等)
描述
给定两个字符串 s 和 p找到 s 中所有 p 的 异位词 的子串返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串包括相同的字符串。
示例 1:
输入: s “cbaebabacd”, p “abc” 输出: [0,6] 解释: 起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。 起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。 leetcode链接 方法一滑动窗口 我们定义一个长度为p.size()大小的窗口在s中不断移动此大小固定的窗口并且比较窗口内的元素是否由p中的元素组成考虑到题目给出的字符串都是由26个小写的字母组成因此我们比较窗口内的元素可以统计窗口内每个字母出现的次数和p中每个字母出现的次数是否相同如果相同那么此窗口即为所求子串因此我们定义两个大小为26的vector1和vector2分别存储窗口中单词出现的次数和p中单词出现的次数。 时间复杂度o(m(n-m)*26) 需要o(m)来初始化vector存储单词的数量后面有n-m个窗口因此需要比较n-m次单词的数量每次比较需要比较26个元素因此时间复杂度为o((n-m)*26) 空间复杂度o(1) 只需要常量级的空间 我们先统计第一个窗口的字母数量再循环统计后面窗口的字母数量如图所示一边删除前一个单词第一个指针一边增加后一个窗口字母后一个指针即可得到当前指针内窗口字母的数量
vectorint findAnagrams(string s, string p) {int n s.size();int m p.size();vectorint ans;//s的大小小于p时候肯定不存在满足条件子串if(nm){return ans;}vectorint sCount(26,0);vectorint pCount(26,0);//先统计第一个窗口单词出现的次数for(int i0;im;i){sCount[s[i]-a];pCount[p[i]-a];}//比较第一个窗口是否为所求子串if(sCountpCount){ans.push_back(0);}for(int i0;in-m;i){//统计下一个窗口的字母数量sCount[s[i]-a]--;sCount[s[im]-a];if(sCountpCount){ans.push_back(i1);}}return ans;
}方法二 考虑我们方法一花费的时间主要在滑动窗口每种字母数量与p的对比上因此我们方法二不再统计每个窗口的字母数量我们存储滑动窗口和p的每种单词的数量差值并且用differ记录数量不一样的字母的个数那么如果differ0,表示所有字母的数量都相同那么该窗口即为所求窗口因此我们通过判断differ是否为0来判断是否为子串省去了判断每一种字母数量的时间。 时间复杂度o(mn-m) om用来初始化vector后面有n-m个窗口需要比较比较的时间复杂度为o1 空间复杂度o(1) 申请了常量级的空间 vectorint findAnagrams(string s, string p) {int n s.size();int m p.size();vectorint ans;if(nm){return ans;}vectorint count(26,0);for(int i0;im;i){count[s[i]-a];count[p[i]-a]--;}int differ 0;for(int i0;i26;i){//统计第一个窗口不同数量字母的个数if(count[i]!0){differ;}}if(differ 0){//如果没有则第一个窗口即为所求的子串ans.push_back(0);}for(int i0;in-m;i){if (count[s[i] - a] 1) { // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同--differ;} else if (count[s[i] - a] 0) { // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同differ;}--count[s[i] - a];if (count[s[i m] - a] -1) { // 窗口中字母 s[ipLen] 的数量与字符串 p 中的数量从不同变得相同--differ;} else if (count[s[i m] - a] 0) { // 窗口中字母 s[ipLen] 的数量与字符串 p 中的数量从相同变得不同differ;}count[s[i m] - a];if(differ0){ans.push_back(i1);}}return ans;
}题目 串联所有单词的子串(2困难)
描述 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如如果 words [“ab”,“cd”,“ef”] 那么 “abcdef” “abefcd”“cdabef” “cdefab”“efabcd” 和 “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] 也是可以的。
leetcode链接 方法一 类似于上题的方法二我们用differ记录窗口单词出现次数和words中出现次数之差如果differ为空那么说明窗口中的单词和words中的单词相同。 定义n为words的大小m为words中每个单词的长度ls为s字符串的长度那么每个窗口的长度应该为nm。首先我们需要将字符串s分成单词组即分成一组有长度为m的单词组成的单词组那么应该有m种分法这里解释一下为什么是m种假如字符串0123456按两个一分那么有0 12 34 56和01 23 45 6这两种分法如果按三个一分那么有0 123 456和01 234 56和0123 456这三种分法以此类推字符串按m个一分一共有m种分法然后对于这里的每一种分法我们进行滑动窗口来判断当前窗口是否为所求的子串窗口一次移动一个单词的长度即为移动m那么即为左边减去一个单词右边加上一个单词。 时间复杂度o(lsm) 一共有m种分法每一种分法我们都需要利用滑动窗口而滑动窗口的时间复杂度为o(ls)所以总时间复杂度为o(lsm) 空间复杂度o(nm) 一共m种分法每一种都需要定义大小为n的unordered_map vectorint findSubstring(string s, vectorstring words) {int n words.size();int m words[0].size();int ls s.size();vectorint ans;//枚举每一种单词组合的起始位置 for(int i0;imin*mls;i){unordered_mapstring,int differ;for(int j 0;jn;j){//统计窗口中单词出现的次数 differ[s.substr(i j * m, m)];}for(int j0;jn;j){//如果窗口中单词出现的次数和words中一样那么在differ中删去 if(--differ[words[j]]0){differ.erase(words[j]);}}//ls-m*n为剩余的字母数量滑动窗口每次移动一个单词的长度 for(int starti;startls-m*n1;startm){if(start!i){//右边加入一个单词 string word s.substr(start(n-1)*m,m);if(differ[word]0){differ.erase(word);}//左边减去一个单词 word s.substr(start-m,m);if(--differ[word]0){differ.erase(word);}}//如果窗口中所有单词出现的次数和words一样则为所求子串 if(differ.empty()){ans.push_back(start);}}}return ans;
}
