LeetCode : 438. Find All Anagrams in a String 查找所有异位字符串

偏执的太偏执、 2021-06-24 16:11 288阅读 0赞

**试题**  
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”.  
**代码**  
逻辑思路,代码还可以继续优化，比如使用数组比较是否出现Arrays.equals(temp, map)。

class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            ArrayList<Integer> out = new ArrayList<>();
            if(s==null || s.length()==0) return out;
    
            int[] alphas = new int[26];
            for(char c : p.toCharArray()) alphas[c-'a'] += 1;
            String key = toStr(alphas);
            
            for(int i=0; i<s.length() && (i+p.length())<=s.length(); i++){
                String tmp = s.substring(i,i+p.length());
                Arrays.fill(alphas, 0);
                for(char c : tmp.toCharArray()) alphas[c-'a'] += 1;
                if(key.equals(toStr(alphas))){
                    out.add(i);
                }
            }
            return out;
            
        }
        
        public String toStr(int[] alphas){
            StringBuilder tmp = new StringBuilder();
            for(int a : alphas){
                tmp.append(a);
                tmp.append("#");
            }
            return tmp.toString();
        }
    }