asp网站无法上传图片,山东建设网站首页,网站规划与设计范文,深圳建筑人才网招聘信息给定两个字符串 s 和 p#xff0c;找到 s 中所有 p 的 异位词 的子串#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。
示例 1:
输入: s cbaebabacd, p abc
输出: [0,6]
解释:
起始索引等于 0 的子串是 cba, 它是 …给定两个字符串 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.首先关键在与如何将两个字符串的比较转化为两个字符数组的比较。
2.可以建立两个长度为26的字符数组通过比较两个字符数组中字母出现的频数便可以得出是否为字母异位词。
3.遍历字符数组将字符装进滑动窗口中满了之后比较两个字符数组如果相等将第一个加进来的字符索添加进结果中然后更新滑动窗口。
class Solution {public ListInteger findAnagrams(String S, String P) {char[] s S.toCharArray();char[] p P.toCharArray();int[] tar new int[26];int[] tmp new int[26];ListInteger res new ArrayList();int n s.length;int m p.length;for (int i 0; i m; i) {int idp p[i] - a;tar[idp]; }for (int i 0; i n; i) {int ids s[i] - a; tmp[ids];if (i m - 1) {continue;}if (Arrays.equals(tar, tmp)) {res.add(i - m 1);}int out s[i - m 1] - a;tmp[out]--;}return res;}
}
