438. Find All Anagrams in a String

Posted on | Edited on | Views:

LeetCode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    private String sortedString(String str){
        char[] chs=str.toCharArray();
        Arrays.sort(chs);
        return new String(chs);
    }
    public List<Integer> findAnagrams(String s, String p) {
        String sortedP=sortedString(p);
        int strLen=p.length();
        List<Integer> res=new ArrayList<>();
        for(int i=0;i<=s.length()-strLen;i++){
            if(sortedString(s.substring(i,i+strLen)).equals(sortedP)){
                res.add(i);
            }
        }
        return res;
    }
}

constant-time slice: Bitmasks or Rabin-Karp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// rolling hash algorithm
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen=s.length(),pLen=p.length();
        if(sLen<pLen) return new ArrayList<>();
        
        int[] pCount=new int[26];
        int[] sCount=new int[26];
        for(int i=0;i<pLen;i++){
            pCount[(int)(p.charAt(i)-'a')]++;
        }
        
        List<Integer> res=new ArrayList<>();
        for(int i=0;i<sLen;i++){
            sCount[(int)(s.charAt(i)-'a')]++;
            if(i>=pLen){
                sCount[(int)(s.charAt(i-pLen)-'a')]--;
            }
            if(Arrays.equals(pCount,sCount)){
                res.add(i-pLen+1);
            }
        }
        return res;
    }
}

0%