视频网站砸钱做生态,网站建设需求有哪些,敖降网站建设,网站导航条找到字符串中所有字母异位词
给定两个字符串 s 和 p#xff0c;找到 s 中所有 p 的 异位词 的子串#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串#xff08;包括相同的字符串#xff09;
示例 1:
输入: s …找到字符串中所有字母异位词
给定两个字符串 s 和 p找到 s 中所有 p 的 异位词 的子串返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串包括相同的字符串
示例 1:
输入: s cbaebabacd, p abc
输出: [0,6]
解释:
起始索引等于 0 的子串是 cba, 它是 abc 的异位词。
起始索引等于 6 的子串是 bac, 它是 abc 的异位词。示例 2:
输入: s abab, p ab
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 ab, 它是 ab 的异位词。
起始索引等于 1 的子串是 ba, 它是 ab 的异位词。
起始索引等于 2 的子串是 ab, 它是 ab 的异位词。提示:
1 s.length, p.length 3 * 10^4s 和 p 仅包含小写字母
超时代码
用滑动窗口去遍历整个字符串每次遍历到一个字串就sort一次再与sort好的字符串 p 比较当字符串长度过长时这个做法肯定会超时.
class Solution {
public:vectorint findAnagrams(string s, string p) {vectorint ans;int len_s s.length(); // s的长度int len_p p.length(); // p的长度sort(p.begin(), p.end()); // 对p进行排序int i 0, j i len_p - 1; // 滑动窗口while (j len_s) {// 将滑动窗口中的字串取出存放到tmp中string tmp ;tmp.append(s.substr(i, len_p));sort(tmp.begin(), tmp.end());if (!tmp.compare(p)) { // 若两个字符串相等ans.push_back(i);}i, j; // 往后移动滑动窗口}return ans;}
};正确做法
同样的滑动窗口思路但是判断字符串是否是字母异位词改用长度为26的数组来记录遍历到的字串中字母出现的次数与 p 字符串中字母出现的次数若两者相同则是字母异位词。代码如下
class Solution {
public:vectorint findAnagrams(string s, string p) {int len_s s.length(); // s的长度int len_p p.length(); // p的长度if (len_s len_p) return vectorint();vectorint ans;vectorint sCNT(26); // 记录s串中字母出现次数vectorint pCNT(26); // 记录p串中字母出现次数for (int i 0; i len_p; i) {sCNT[s[i] - a];pCNT[p[i] - a];}// 0位置开始的滑动窗口中的字符串与目标字符串互为字母异位if (sCNT pCNT) ans.push_back(0); for (int i 0; i len_s - len_p; i) {// 移动窗口--sCNT[s[i] - a];sCNT[s[i len_p] - a];if (sCNT pCNT) {ans.push_back(i 1);}}return ans;}
};
