Leetcode 438-找到字符串中所有字母异位词

首先就是最简单的暴力破解。把字符串p转化为char数组然后排序。接着就是遍历s，每次取长度和p一样的子串，排序之后和p比较，如果一样的话，就把当前下标加入到list中。

class Solution {
public List<Integer> findAnagrams(String s, String p) {
char[] c = p.toCharArray();
Arrays.sort(c);
String target = new String(c);
int length = p.length();
List<Integer> indexs = new ArrayList<>();
for(int i = 0; i < s.length() – length + 1; i++){
String subStr = s.substring(i, i+length);
char[] subC = subStr.toCharArray();
Arrays.sort(subC);
String tempStr = new String(subC);
if(tempStr.equals(target)){
indexs.add(i);
}
}
return indexs;
}
}

然而耗时有点长了。因此着手改进一下：题目里给定了字符串中只包含小写字母，因此可以用之前学过的一个方法，计算子串中字母出现的次数，最后合成一个string，判断是否一样只需要比较这个string就可以了，避免了排序的复杂度。

class Solution {
public List<Integer> findAnagrams(String s, String p) {
String target = letterCount(p);
int length = p.length();
List<Integer> indexs = new ArrayList<>();
for(int i = 0; i < s.length() – length + 1; i++){
String subStr = s.substring(i, i+length);
String tempStr = letterCount(subStr);
if(tempStr.equals(target)){
indexs.add(i);
}
}
return indexs;
}

public String letterCount(String a){
char[] c = a.toCharArray();
int[] count = new int[26];
for(char letter : c){
count[(int)(letter – 'a')]++;
}
StringBuffer sb = new StringBuffer();
for(int i = 0; i<26; i++){
if(count[i]>0){
sb.append(count[i]);
sb.append((char)('a' + i));
}
}
return sb.toString();
}
}

方法一：定长滑窗

提升不大，看了艾府的答案，继续优化了一下。因为数组其实可以用equals直接来比较，所以不用再转换成String来比了。另一个点就是对于定长窗口，直接维护一个int数组来存元素出现次数就足够了，每次比较一下，如果相同就把left下标加入到list，不相同就去掉最左边的字母，然后循环。原来的方法是每次提取substring，然后创建一个新数组，这样会显著增加消耗。

class Solution {
public List<Integer> findAnagrams(String s, String p) {
char[] c = p.toCharArray();
int[] countP = new int[26];
for(char letter : c){
countP[(int)(letter – 'a')]++;
}
int length = p.length();
List<Integer> indexs = new ArrayList<>();

int[] countS = new int[26];
for(int i = 0; i < s.length(); i++){
countS[(int)(s.charAt(i) – 'a')]++;
int left = i – p.length() + 1;
if(left < 0){
continue;
}
if(Arrays.equals(countP, countS)){
indexs.add(left);
}
countS[(int)(s.charAt(left) – 'a')]–;
}
return indexs;
}
}

方法二：不定长滑窗

同样是艾府大神给的方法。大致就是每次判断新进入的字母的数量是否超过了目标字符串中该字母的数量，如果超出了，那么就移动左指针，直到其数量小于等于目标字符串。因为当前滑窗中的每个字母数量都要保持小于等于目标字符串的，因此当2者长度相同的时候，该字符串即为目标字符串的异位词。

class Solution {
public List<Integer> findAnagrams(String s, String p) {
char[] c = p.toCharArray();
int[] countP = new int[26];
for(char letter : c){
countP[letter – 'a']++;
}
int length = p.length();
List<Integer> indexs = new ArrayList<>();

int[] countS = new int[26];
int left = 0;
for(int i = 0; i < s.length(); i++){
countS[(int)(s.charAt(i) – 'a')]++;
while(countS[(int)(s.charAt(i) – 'a')] > countP[(int)(s.charAt(i) – 'a')]){
countS[s.charAt(left) – 'a']–;
left++;
}
if(p.length() == i – left +1){
indexs.add(left);
}
}
return indexs;
}
}

下面附上艾府大神的讲解，讲的还是很好的，简单易懂。