Java 13ms solution, fast than below shortest solution by sliding window, Why?


  • 0

    Update:
    after release my solution, I saw the Shortest/Concise JAVA O(n) Sliding Window Solution, it is very great. But my complexity code looks like more fast. so still share just for fun.

    To len (P) as the window, traverse the s from left to right.
    We use the pre to show whether the last traversal was successful in finding the Anagrams. when pre = true, there will be three kinds of situations:
    1、s[start -1] == s[end] direct add
    2、the new char of s[end] is not in p
    3、the new char of s[end] is in p, but s[end] is not the s[start - 1]

    by using this method, we can save some unnecessary calculations.

    public List<Integer> findAnagrams(String s, String p) {
            List<Integer> res = new ArrayList<>();
            if (p.length() > s.length()) return res;
    
            int[] base = new int[26];
            int len = p.length();
            for (int i = 0; i < len; i++) {
                base[p.charAt(i) - 'a']++;
            }
    
            int[] count = new int[26];
            boolean pre = false;  //is last combination is a Anagrams
            int start = 0;  //start of len(p) window in s
            int end = start + len - 1;  //end of len(p) window in s
            int loop = len;  //the len that we will loop to calculate the sum in every window.
    
            for (; start <= s.length() - len; start++, end++) {
                if (!pre) {
                    for (int i = loop; i > 0; i--) {
                        count[s.charAt(end - i + 1) - 'a']++;
                    }
    
                    int i = 0;
                    while (i < base.length) {
                        if (base[i] != count[i]) break;
                        i++;
                    }
                    if (i == base.length) {
                        res.add(start);
                        pre = true;
                    } else {
    //                    Arrays.fill(count, 0);  //optimization
                        count[s.charAt(start) - 'a']--;
                        loop = 1;
                    }
                } else {
                    char last = s.charAt(end);
                    //Three kinds of situations
                    //1、s[start -1] == s[end] direct add
                    //2、the new char of s[end] is not in p
                    //3、the new char of s[end] is in p, but s[end] is not the s[start - 1]
                    if (last == s.charAt(start - 1)) res.add(start);
                    else if (base[last - 'a'] == 0) {
                        Arrays.fill(count, 0);
                        loop = len;
                        start = end;
                        end = start + len - 1;
                        pre = false;
                    } else {
                        int i = start;
                        count[s.charAt(i - 1) - 'a']--;
                        for (; i < end; i++) {
                            char cur = s.charAt(i);
                            if (cur != last) count[cur - 'a']--;
                            else break;
                        }
                        //space char is i - start + 1, Backward extension
                        loop = i - start + 1;
                        //i + 1 ==> start
                        start = i;
                        end = start + len - 1;
                        pre = false;
                    }
                }
    
            }
            return res;
        }
    

Log in to reply
 

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