647.Substring Anagrams

1.Description(Easy)

Given a stringsand anon-emptystringp, find all the start indices ofp's anagrams ins.

Strings consists of lowercase English letters only and the length of both stringssandpwill not be larger than 40,000.

The order of output does not matter.

Example

Given s ="cbaebabacd"p ="abc"

return[0, 6]

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".

Tags

Hash Table Amazon

2.Code

String.substring()

 public List<Integer> findAnagrams(String s, String p) {

        List<Integer> result = new ArrayList<Integer>();
        if (s.length() < p.length()) {
            return result;
        }
        int len = p.length();
        for (int i = 0; i < s.length()-len+1; ++i ) {
            String current = s.substring(i,i+len);
            if (isAnagrams(current,p)){
                result.add(i);
            }
        }
        return result;
    }

    public boolean isAnagrams(String a, String b) {
        if (a.length() != b.length()) {
            return false;
        }
        int[] letter = new int[26];
        for (int i = 0; i < a.length(); ++i) {
            char currenta = a.charAt(i);
            char currentb = b.charAt(i);
            letter[currenta-'a']++;
            letter[currentb-'a']--;
        }

        for (int i = 0; i < 26; i++) {
            if (letter[i] != 0){
                return false;
            }
        }
        return true;
    }