Java Easy to understand solution


  • 0
    A

    The sub 20ms sliding windows solution is so brilliant that I feel hard to understand. Here's my own not so smart solution that runs about 260ms.

    Note: it is originally using hashmap for statistics but ran out of time, array is much faster for sure.

    public class Solution {
    int[] buildStats(String s, int start, int len){
    int[] stats = new int[26];
    for(int i=start;i<start+len;i++){
    stats[s.charAt(i)-'a']++;
    }
    return stats;
    }
    private boolean featureMatch(String s,int index,int len,int[] stats){
    int[] newStats = new int[26];
    System.arraycopy(stats,0,newStats,0,26);
    for(int i=index;i<index+len;i++){
    char c = s.charAt(i);
    newStats[c-'a']--;
    if(newStats[c-'a']<0)return false;
    }
    for(int i=0;i<26;i++){
    if(newStats[i]>0)return false;
    }
    return true;
    }
    public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<Integer>();
    if(s==null ||s.length()==0||s.length()<p.length())return result;
    //build up pattern feature
    int[] statsP = buildStats(p,0,p.length());

        for(int i=0;i<=s.length()-p.length();i++){
            if(featureMatch(s,i,p.length(),statsP)){
                result.add(i);
            }
        }
        return result;
    }
    

    }


Log in to reply
 

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