题目描述
给定两个字符串 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 * 104s和p仅包含小写字母
解法一
思路：
滑动窗口方法，窗口大小为p字符串的长度，窗口内的字符串若与p字符串为异位词，则记录位置，之后滑动窗口。对于异位词的判断采用数组计数法，创建一个int[26]的数组，当p中字符出现一次，则该位置上的数组值加1，对于滑动窗口内，每个字符出现一次，该位置值减1，若数组所有值为0，则为异位词。
代码：
import java.util.*;
import java.util.function.IntPredicate;public class leetcode_009 {public static List<Integer> findAnagrams(String s, String p) {//窗口的选择，如何进行遍历，重复？List<Integer> ans = new ArrayList<>();//字符计数法int[] pChars=new int[26];//统计每个字符出现的频率for(int i=0; i<p.length(); i++){pChars[p.charAt(i)-'a']++;}int windowLen=p.length();//将s串转化为字符数组char[] sChars=s.toCharArray();for(int i=0; i<sChars.length-windowLen+1; i++){//频率数组的拷贝int[] pCharsCopy=Arrays.stream(pChars).toArray();for(int j=i; j-i<windowLen; j++){pCharsCopy[sChars[j]-'a']--;}if(Arrays.stream(pCharsCopy).allMatch(value -> value==0))ans.add(i);}return ans;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String line1 = sc.nextLine();String line2 = sc.nextLine();List<Integer> res = findAnagrams(line1,line2);System.out.println(res);}
}解法二
思路：
来自官方的解答，创建两个的数组，也是采用滑动窗口，窗口大小为p串长度，从s串的第一个窗口开始，首先s串出现一个字符，数组对应位置+1，p中出现一个字符，对应位置+1，第一窗口统计结束，如果数组相等，则第一个窗口内就为异位词，之后滑动窗口，窗口最左侧字符出去，对应位置数组值-1，窗口后一个字符进入，对应位置数组值+1，此时判断数组值是否相等。
代码：
class Solution {public List<Integer> findAnagrams(String s, String p) {int sLen = s.length(), pLen = p.length();// 如果s的长度小于p，直接返回空列表if (sLen < pLen) {return new ArrayList<Integer>();}List<Integer> ans = new ArrayList<Integer>();int[] sCount = new int[26]; // 用于统计s中当前窗口的字符频率int[] pCount = new int[26]; // 用于统计p的字符频率// 初始化频率统计for (int i = 0; i < pLen; ++i) {++sCount[s.charAt(i) - 'a']; // 统计s的前pLen个字符++pCount[p.charAt(i) - 'a']; // 统计p的所有字符}// 检查第一个窗口是否是异位词if (Arrays.equals(sCount, pCount)) {ans.add(0);}// 滑动窗口：从0到sLen-pLen-1for (int i = 0; i < sLen - pLen; ++i) {// 移除窗口最左侧的字符--sCount[s.charAt(i) - 'a'];// 添加窗口右侧的新字符++sCount[s.charAt(i + pLen) - 'a'];// 检查当前窗口是否是异位词if (Arrays.equals(sCount, pCount)) {ans.add(i + 1); // 添加当前窗口的起始索引}}return ans;}
}
解法三
思路：
也是官方解答，对滑动窗口进行优化，采用一个数组进行统计，窗口大小为p串长度，从s串的第一个窗口开始，首先s串出现一个字符，数组对应位置+1，p中出现一个字符，对应位置-1，第一窗口统计结束，判断数组不为0的个数为diff，这个就代表差异字母个数，如果diff为0，则第一个窗口内就为异位词.采用diff值来进行判断，diff表示窗口内不同字母的数量，对于每个字母差多少不理会，如bb和ab，diff为1，只是一个字母不同。移动窗口时，窗口左侧字符要出去，如果count[s.charAt(i) - 'a'] == 1表示该字符窗口内多一个，移除后，窗口内字符与p字符相等，则diff-1，去除了这个差异，如果count[s.charAt(i) - 'a'] == 0表示该字符窗口内与p相等，移除后，窗口内字符与p字符不同，则diff+1，添加这个差异，对于count[s.charAt(i) - 'a'] == 2这种情况，diff不变，因为移除后窗口内字符与p还是不同，同理，添加字符也是如此。
代码：
class Solution {public List<Integer> findAnagrams(String s, String p) {int sLen = s.length(), pLen = p.length();// 如果s的长度小于p，直接返回空列表if (sLen < pLen) {return new ArrayList<Integer>();}List<Integer> ans = new ArrayList<Integer>();int[] count = new int[26]; // 用于记录字符频率差异// 初始化频率差异统计// 对s中的字符增加计数，对p中的字符减少计数for (int i = 0; i < pLen; ++i) {++count[s.charAt(i) - 'a']; // s中的字符增加计数--count[p.charAt(i) - 'a']; // p中的字符减少计数}// 计算初始差异程度int differ = 0;for (int j = 0; j < 26; ++j) {if (count[j] != 0) {++differ;}}// 检查第一个窗口是否是异位词if (differ == 0) {ans.add(0);}// 滑动窗口for (int i = 0; i < sLen - pLen; ++i) {// 处理要移除的字符 (s[i])if (count[s.charAt(i) - 'a'] == 1) {// 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同--differ;} else if (count[s.charAt(i) - 'a'] == 0) {// 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同++differ;}--count[s.charAt(i) - 'a']; // 移除字符// 处理要添加的字符 (s[i+pLen])if (count[s.charAt(i + pLen) - 'a'] == -1) {// 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同--differ;} else if (count[s.charAt(i + pLen) - 'a'] == 0) {// 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同++differ;}++count[s.charAt(i + pLen) - 'a']; // 添加字符// 检查当前窗口是否是异位词if (differ == 0) {ans.add(i + 1);}}return ans;}
}