自己做个网站好还是做别人会员好,桂林网上商城,唐山做企业网站,威海外贸网站建设怎么样给定两个字符串 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;}
}
