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".
//My Solution
public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if (s == null || p == null) {
            return new ArrayList<>();
        }
        // Scan p, add to counter.
        List<Integer> result = new ArrayList<>();
        int[] counter = new int[256];
        for (char c : p.toCharArray()) {
            counter[c]++;
        }
        // Scan s, sliding window, length = p.length()
        int left = 0;
        int right = 0;
        int maxLen = p.length();
        int dif = p.length();
        for (; right < s.length(); right++) {
            counter[s.charAt(right)]--;
            if (counter[s.charAt(right)] >= 0) dif--;
            if (right - left == maxLen - 1) {
                if (dif == 0) result.add(left);
                if (counter[s.charAt(left)] >= 0) {
                    dif++;
                }
                counter[s.charAt(left)]++;
                left++;
            }
        }
        return result;
    }
}

// From reference
public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<Integer>();
        int NumberOfDeference = p.length();  //差异度指数
        int left=0,right=0;  //窗口左右指针
        int[] asciiChars = new int[256];  
//记录p中字符有哪些及其数量的数组
        for (int i = p.length() - 1; i>=0; --i)
          {     ++asciiChars[p.charAt(i)];      } //记录完毕
        
        for(;right<s.length();right++){ //滑动右窗口
            asciiChars[s.charAt(right)]--;  //在该字符相应位置减一
            if(asciiChars[s.charAt(right)]>=0) NumberOfDeference--; 
//如果加进来的那个在p中,NumberOfDeference减一
            if(right-left == (p.length()-1)){
 //如果这时窗口大小为p.length()
                if(NumberOfDeference==0) result.add(left);  
//这时出现一次匹配,将左窗口加到result中
                //下面是滑动左窗口的操作
                if(asciiChars[s.charAt(left)]>=0) {
                    NumberOfDeference++; 
//如果被踢出的那个在p中,NumberOfDeference加一
                }
                asciiChars[s.charAt(left)]++;
//数组中相应字符计数位置加回来
                left++; //左窗口向右滑动
            }
        }
        return result;
    }

Reference:
http://qkxue.net/info/185575/leetcode-Find-All-Anagrams-String-java-438

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