O(n) Java Solution with Hash Table + Sliding Window


  • 0
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s == null || p == null || s.length() < p.length()) {
            return result;
        }
        Map<Character, Integer> countMap = getCountMap(p);
        int match = 0;
        for (int i = 0; i < s.length(); i++) {
            Integer count = countMap.get(s.charAt(i));
            if (count != null) {
                countMap.put(s.charAt(i), count - 1);
                if (count == 1) {
                    match++;
                }
            }
            if (i >= p.length()) {
                count = countMap.get(s.charAt(i - p.length()));
                if (count != null) {
                    countMap.put(s.charAt(i - p.length()), count + 1);
                    if (count == 0) {
                        match--;
                    }
                }
            }
            if (match == countMap.size()) {
                result.add(i - p.length() + 1);
            }
        }
        return result;
    }
    
    private Map<Character, Integer> getCountMap(String p) {
        Map<Character, Integer> countMap = new HashMap<>();
        for (int i = 0; i < p.length(); i++) {
            Integer count = countMap.get(p.charAt(i));
            count = count == null ? 1 : count + 1;
            countMap.put(p.charAt(i), count);
        }
        return countMap;
    }

Log in to reply
 

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