Java Sliding Window solution


  • 0
    S

    Just use a sliding window, and record the different character numbers. if the different numbers is 0, record it. Here is the codes:

     public List<Integer> findAnagrams(String s, String p) {
        if (s.length() < p.length()) {
            return new ArrayList<>();
        }
    
        int[] chars = new int[128];
        int[] sc = new int[128];
        for (int i = 0; i < p.length(); ++i) {
            chars[p.charAt(i)]++;
        }
        for (int i = 0; i < p.length() - 1; ++i) {
            if (chars[s.charAt(i)] > 0) {
                sc[s.charAt(i)]++;
            }
        }
    
        int diffNum = 0;
        for (int i = 'a'; i <= 'z'; ++i) {
            if (sc[i] != chars[i]) {
                diffNum += Math.abs(sc[i] - chars[i]);
            }
        }
    
        List<Integer> result = new ArrayList<>();
        for (int i = p.length() - 1; i < s.length(); ++i) {
            char ch = s.charAt(i); // char to be added
            if (chars[ch] > 0) {
                diffNum += sc[ch] >= chars[ch] ? 1 : -1;
                sc[ch]++;
            }
            if (diffNum == 0) {
                result.add(i - p.length() + 1);
            }
            ch = s.charAt(i - p.length() + 1); // char to be deleted
            if (chars[ch] > 0) {
                diffNum += sc[ch] > chars[ch] ? -1 : 1;
                sc[ch]--;
            }
        }
    
        return result;
    }

Log in to reply
 

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