Simple JAVA solution Sliding Window Algo


  • 0
    R

    '''
    public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
    List<Integer> l=new ArrayList<>();
    if(s.length()<p.length())return l;

     // As only small alphabets otherwise in general case length will be 256
    // two arrays one to store frequency of characters given pattern
    // second to store frequency of characters in first window
    
        int cp[]=new int[26];
        int cs[]=new int[26];
    

    for(int i=0;i<p.length();i++)
    {
    cp[p.charAt(i)-'a']++;
    cs[s.charAt(i)-'a']++;
    }
    // compare if both arrays are equal
    // add the index of first character of present window
    //add next character of the new window and delete the first character of previous
    int j=0;
    for(j=p.length();j<s.length();j++)
    {
    if(compare(cp,cs))
    l.add(j-p.length());
    cs[s.charAt(j)-'a']++;
    cs[s.charAt(j-p.length())-'a']--;
    }

    // the last window should be compared outside the loop

        if(compare(cp,cs))
         l.add(j-p.length());
        return l;
    }
    

    // Function to compare whether two arrays are equal

    public boolean compare(int cp[],int cs[])
    {
        for(int i=0;i<26;i++)
        if(cp[i]!=cs[i])return false;
        return true;
    }
    

    }
    '''


Log in to reply
 

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