LeetCode - 438. Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of p‘s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

这道题目看似简单，里面玄机非常多，建议手写试试

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int l = p.length();
        int x=0;
        int[] chars = new int[26];
        List result = new ArrayList();
        for(int i=0;i<p.length();i++){
            chars[p.charAt(i) - 'a'] ++;
        }
        while(x<s.length()){
            int count=0;
            int[] cp = chars.clone();
            if(chars[s.charAt(x) - 'a'] != 0 && x+l<=s.length()){
                count ++;
                int tmp = 1;
                cp[s.charAt(x) - 'a']--;
                while(tmp<l){
                    
                    if(cp[s.charAt(x+tmp) - 'a'] > 0){
                        cp[s.charAt(x+tmp) - 'a']--;
                        count++;
                    }
                    tmp++;
                }
                if(count == l){
                    result.add(x);
                }
            }
            x++;
        }
        return result;
    }
}

看完了？留个评分呗？

[0人评了分，平均: 0/5]