Java sliding window


  • 0
    D
    public class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> bIndices = new ArrayList<>();
            if (s == null || s.length() == 0) {
                return bIndices;
            }
            Map<Character, Integer> freq = new HashMap<>();
            for (int i = 0; i < p.length(); i++) {
                char ch = p.charAt(i);
                freq.put(ch, freq.containsKey(ch) ? freq.get(ch) + 1 : 1);
            }
            for (int bIndex = 0, eIndex = 0; eIndex < s.length(); eIndex++) {
                char candidate = s.charAt(eIndex);
                while (!freq.containsKey(candidate) && bIndex <= eIndex) {
                    if (bIndex < eIndex) {
                        char bch = s.charAt(bIndex);
                        freq.put(bch, freq.containsKey(bch) ? freq.get(bch) + 1 : 1);
                    }
                    bIndex++;
                }
                if (bIndex <= eIndex) {
                    freq.put(candidate, freq.get(candidate) - 1);
                    if (freq.get(candidate) == 0) {
                        freq.remove(candidate);
                    }
                    if (freq.size() == 0) {
                        bIndices.add(bIndex);
                        char bch = s.charAt(bIndex++);
                        freq.put(bch, freq.containsKey(bch) ? freq.get(bch) + 1 : 1);
                    }
                }
            }
            return bIndices;
        }
    }
    

Log in to reply
 

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