崇文手机网站建设,建设银行客户投诉网站,sem专业培训公司,wordpress 评论点赞题目链接 剑指 Offer II 015. 字符串中的所有变位词 mid 题目描述
给定两个字符串 s和 p#xff0c;找到 s中所有 p的 变位词 的子串#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。
变位词 指字母相同#xff0c;但排列不同的字符串。
示例 1#xff1a; 输…题目链接 剑指 Offer II 015. 字符串中的所有变位词 mid 题目描述
给定两个字符串 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” 的变位词。 提示
1s.length,p.length3∗1041 s.length, p.length 3 * 10^41s.length,p.length3∗104s和 p仅包含小写字母
分析
先用一个 cnt[26]记录p中字符出现的次数的负数。
用两个指针 i和 j组成滑动窗口遍历 s。向右遇到一个新的字符cnt[s[j]]。当 cnt[s[j] 0时说明区间 [i,j]中有多余的字符。需要移动指针 i从窗口中去掉多余的字符cnt[s[i]]--。
当 cnt[s[j] 0且 j - i 1 s2.length时说明此时 s[i,j]就是 p的变位词。记录区间起点 i到答案 ans中。
时间复杂度O(n)O(n)O(n)
C代码
class Solution {
public:vectorint findAnagrams(string s, string p) {int m s.size() , n p.size();int cnt[26] {0};for(auto c:p) cnt[c - a]--;vectorint ans;for(int i 0,j 0;j m;j){cnt[s[j] - a];while(cnt[s[j] - a] 0){cnt[s[i] - a]--;i;}if(j -i 1 n) ans.push_back(i);}return ans;}
};Java代码
class Solution {public ListInteger findAnagrams(String s, String p) {ListInteger ans new ArrayList();int m s.length();int n p.length();int[] cnt new int[26];for(var c:p.toCharArray()) cnt[c - a]--;for(int i 0,j 0;j m;j){cnt[s.charAt(j) - a];while(cnt[s.charAt(j) - a] 0){cnt[s.charAt(i) - a]--;i;}if(j - i 1 n) ans.add(i);}return ans;}
}
