438. Find All Anagrams in a String

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 Solutions:

anagram 的定义是两个单词里出现的字母相同。

方法1：naive，把string里每一个char的len = p的substring都检查一遍

Time: O(n), n = length of s

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s == null || p == null || s.length() == 0 || p.length() == 0) return res;
        
        int len = p.length();
        for (int i = 0; i <= s.length() - len; i++) {
            if (isAna(s.substring(i, i + len), p)) {
                res.add(i);
            }
        }
        
        return res;
    }
    
    private boolean isAna(String s, String p) {
        int[] hash = new int[26];
        for (int i = 0; i < p.length(); i++) {
            hash[p.charAt(i) - 'a']++;
            hash[s.charAt(i) - 'a']--;
        }
        for (int c : hash) {
            if (c != 0) return false;
        }
        return true;
    }
}

方法2：

• 先创建一个256大小的int array，把p里所有字符出现的频率记录下来。用counter记录p的长度

• 然后用两个指针，left代表sliding window的左边，即单词的开始index，right向右移动创造sliding window。只要right没有到搜索s的最末端，就不停向右移动。

  • 在移动的过程中，right所在的字符如果在p里，就把counter 减1。

  • 检测counter是否为0。如果为0，说明p里的所有字符都已经找到，把left此时的数字加入结果。

  • 无论如何，right所在的字符在int array里的频率减1。然后移动right，right++。

  • 如果此时left和right之间的距离等于p的长度，说明window已经是p的长度。我们需要把left左移，让window继续前进。

    • 首先看此时int array里left所在的数字。如果此数字大于等于0，说明l所在的这个字母在p里出现过，因为没有出现过的字母会是负数。之前counter在这个情况下减去过1，所以此时count++把这个1加回来。

    • 无论如何要把int array里的left所在的字符频率也+1。left再右移，left++。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        
        List<Integer> res = new ArrayList<>();
        if (s == null || p == null || s.length() == 0 || p.length() ==0) return res;
        
        // 记录p里letter出现的频率
        int[] hash = new int[256];
        for (char c : p.toCharArray()) hash[c]++;
        
        //counter is a number to record whether we have a anagram which has equal length as p
        int left = 0, right = 0, counter = p.length(); 
        
        while (right < s.length()) {
            
            // there is p's char in s，把counter减少1
            char curr = s.charAt(right);
            if (hash[curr] >= 1) counter--;
            
            // 如果counter==0，说明每个在p里的字母都在s里找到了
            if (counter == 0) res.add(left);
                
            // hash table decreases the right char by 1    
            hash[curr]--;    
            right++; //move the sliding window to one step right
            
            //if the window's size equals p, then we have to move left (narrow the window) to find the new match window
            if (right - left == p.length()) { 
                // only increase the count if the character is in p，因为之前只有这样的条件才会count--      
                if (hash[s.charAt(left)] >= 0) counter++;
                // 因为之前减少过hash[curr]--, 马上要移动left坐标，所以这里需要加1回来
                hash[s.charAt(left)]++; 
                left++;
            }
        }
        
        return res;
    }
}