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

思路: 这个题目是求给定的pattern的anagram,在给定的字符串中出现的位置; 需要借助两个数组, 一个是给定的pattern数组,用来存pattern中各个字符的出现次数。 另一个长度等同于pattern的滑动窗口,当前window下的各个字符的出现次数。当window遍历给定的字符s的时候,做一下几件事情: 1. window中前一个坐标对应的字符的次数-1; window中新加进来的字符的次数+1. 然后比较当前window下的anagram跟pattern 是否相同。

复杂度: 比较anagram O(1), 遍历O(n).

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s == null || s.length() == 0 || p == null || p.length() == 0) return res;
        if (s.length() < p.length()) return res;
        int[] pattern = new int[26];
        int[] window = new int[26];
        int pLen = p.length();

        for (int i = 0; i < pLen; i++) {
            int pIdx = p.charAt(i) - 'a';
            int sIdx = s.charAt(i) - 'a';
            pattern[pIdx]++;
            window[sIdx]++;
        }
        if (isAnagram(window, pattern)) res.add(0);
        for (int i = pLen; i < s.length(); i++) {
            int preIdx = i - pLen;
            window[s.charAt(preIdx) - 'a']--;
            window[s.charAt(i) - 'a']++;
            if (isAnagram(window, pattern)) res.add(i - pLen + 1);
        }
        return res;
    }
    public boolean isAnagram(int[] window, int[] pattern) {
        for (int i = 0; i < pattern.length; i++) {
            if(window[i] != pattern[i]) return false;
        }
        return true;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s