Java O(n) solution


  • 3
    M
    public 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 len1 = s.length(), len2 = p.length();
            if(len2 > len1) return res;
            int[] anagram = new int[128];
    
            for(int i = 0; i < len2; i++) {
                anagram[s.charAt(i)]++;
                anagram[p.charAt(i)]--;
            }
            int diff = 0;
            for(int i : anagram) {
                if(i != 0) diff++;
            }
            for(int i = len2; i < len1; i++) {
                if(diff == 0) res.add(i - len2);
                char c1 = s.charAt(i);
                char c2 = s.charAt(i - len2);
                if(c1 == c2) continue;
                
                anagram[c1]++;
                anagram[c2]--;
                if(anagram[c1] == 1) diff++;
                else if(anagram[c1] == 0) diff--;
                
                if(anagram[c2] == -1) diff++;
                else if(anagram[c2] == 0) diff--;
            }
            if(diff == 0) {
                res.add(len1 - len2);
            }
            return res;
        }
    }
    

  • 1

    Need some explanation that how diff works...


  • 1
    M

    @linyuan1212 The diff means how many different characters in the sliding window with size len2, for example, s: "cbaebabacd" p: "abc", in the first sliding window "cba", we can know the diff is 0, then move to next "bae", now compared with ""cba, the diff is 2, because there are two different characters, "e" in "bae", and "c" in "cba", thus during the moving, we can just calculate the diff to know whether it is matched or not


  • 0
    M

    Nice and simple solution!!!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.