Same code as 438. Find All Anagrams in a String


  • 0

    This problem can be solved as the same code as 438. Find All Anagrams in a String. Just change the return value

    Using two pointers:

    public class Solution {
        public boolean checkInclusion(String p, String s) {
            if (s == null || s.length() == 0 || p == null || p.length() == 0 || p.length() > s.length()) return false;
            Map<Character, Integer> map = new HashMap<>();
            int count = p.length();
            for (int i = 0; i < p.length(); i++) {
                if (map.containsKey(p.charAt(i))) map.put(p.charAt(i), map.get(p.charAt(i)) + 1);
                else map.put(p.charAt(i), 1);
            }
    
            int j = 0;
            for (int i = 0; i < s.length(); i++) {
                while (j < s.length() && count != 0) {
                    if (map.containsKey(s.charAt(j))) {
                        map.put(s.charAt(j), map.get(s.charAt(j)) - 1);
                        if (map.get(s.charAt(j)) >= 0) count--;
                    }
                    j++;
                }
                if (j - i == p.length() && count == 0) return true;
                if (map.containsKey(s.charAt(i))) {
                    map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
                    if (map.get(s.charAt(i)) > 0) count++;
                }
            }
            return false;
        }
    }
    
    1. Find All Anagrams in a String:
    public class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> ret = new ArrayList<>();
            if (s == null || s.length() == 0 || p == null || p.length() == 0 || p.length() > s.length()) return ret;
            Map<Character, Integer> map = new HashMap<>();
            int count = p.length();
            for (int i = 0; i < p.length(); i++) {
                if (map.containsKey(p.charAt(i))) map.put(p.charAt(i), map.get(p.charAt(i)) + 1);
                else map.put(p.charAt(i), 1);
            }
            
            int j = 0;
            for (int i = 0; i < s.length(); i++) {
                while (j < s.length() && count != 0) {
                    if (map.containsKey(s.charAt(j))) {
                        map.put(s.charAt(j), map.get(s.charAt(j)) - 1);
                        if (map.get(s.charAt(j)) >= 0) count--;
                    }
                    j++;
                }
                if (j - i == p.length() && count == 0) ret.add(i);
                if (map.containsKey(s.charAt(i))) {
                    map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
                    if (map.get(s.charAt(i)) > 0) count++;
                }
            }
            return ret;
        }
    }
    

  • 0
    C
    This post is deleted!

  • 0
    C
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if(s.length() < p.length()) return res;
        int l = p.length();
        for(int i=0; i<=s.length()-l; i++) {
            String sub = s.substring(i, i+l);
            if(isAnagram(sub, p)) res.add(i);
        }
        return res;
    }
    
    private boolean isAnagram(String s1, String s2) {
        int[] counter1 = new int[26];
        int[] counter2 = new int[26];
        for(int i=0; i<s1.length(); i++) {
            counter1[s1.charAt(i)-'a']++;
            counter2[s2.charAt(i)-'a']++;
        }
        if(Arrays.equals(counter1,counter2)) return true;
        return false;
    }

  • 0
    W

    Yes, I use exactly the same code as 438. Here is my version.

    public class Solution {
        public boolean checkInclusion(String s1, String s2) {
            int[] table = new int[26];
            for (char c : s1.toCharArray()) {
                table[c - 'a']++;
            }
            int start = 0, cnt = s1.length();
            for (int end = 0; end < s2.length(); end++) {
                char c = s2.charAt(end);
                if (table[c - 'a'] > 0) {
                    cnt--;
                }
                table[c - 'a']--;
                
                if (cnt == 0) {
                    return true;
                }
                
                if (end - start + 1 == s1.length()) {
                    if (table[s2.charAt(start) - 'a'] >= 0) {
                        cnt++;
                    }
                    table[s2.charAt(start) - 'a']++;
                    start++;
                }
            }
            return false;
        }
    }
    

Log in to reply
 

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