Leetcode Find All Anagrams in a String problem solution

YASH PAL,

In this Leetcode Find All Anagrams in a String problem solution we have Given two strings s and p, return an array of all the start indices of p’s anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Leetcode Find All Anagrams in a String problem solution

Problem solution in Python.

class Solution(object):
    def findAnagrams(self, s, p):
        res = []
        c = collections.Counter(p)
        cur = collections.Counter(s[:len(p)])
        for i in range(len(s)-len(p)+1):
            if cur==c:
                res.append(i)
            if i == len(s)-len(p):
                break
            cur[s[i]]-=1
            if cur[s[i]]==0:
                del cur[s[i]]
            cur[s[i+len(p)]]+=1
        return res

Problem solution in Java.

public List<Integer> findAnagrams(String s, String p) {

        List<Integer> list =new ArrayList<Integer>();
        Map<Character, Integer> map2= createMap(p);
        Map<Character, Integer> map1= new HashMap<Character, Integer> ();

        for(int i=0;i<s.length()-p.length()+1;i++)
        {
            map1= createMap(s.substring(i,i+p.length()));
            if(map1.equals(map2))
                list.add(i);         
        }
        return list;
    }

    public Map<Character, Integer> createMap(String s)
    {
        Map<Character, Integer> map= new HashMap<Character, Integer>();
        for(char c:s.toCharArray())
        {
            if(map.containsKey(c))
                map.put(c,(map.get(c)+1));
            else
                map.put(c, 1);
        }
        return map;
    }
}

Problem solution in C++.

class Solution {
public:
bool isAllZero(vector<int>& nums)
{
    for (int i = 0; i < nums.size(); i++)
        if (nums[i]) return false;
    return true;
}
vector<int> findAnagrams(string s, string p) {
    vector<int> charCount(26, 0);
    vector<int> res;
    int m = (int)p.length(), n = (int)s.length();
    int left = 0;
    if (n < m) return res;
    for (int i = 0; i < m; i++)
        charCount[p[i] - 'a']++;
    for (int i = 0; i < n; i++)
    {
        charCount[s[i] - 'a']--;
        if (i - left + 1 > m)
        {
            charCount[s[left] - 'a']++;
            left++;
        }
        if (i - left + 1 == m && isAllZero(charCount)) res.push_back(left);
    }
    return res;
}
};

Problem solution in C.

void form_p_arr(char* p,int *num2){
    int i=0;
    while (p[i] != '')
    {
        num2[p[i] -'a']++;
        i++;
    }
}

bool check_anagram(char* s,int window_size,int *num2){
 
    int num1[26]={0};
 
    for(int i=0;i < window_size;i++)
    {
        num1[s[i] - 'a']++;
    }
    
   for (int i = 0; i < 26; i++)
    {
        if (num1[i] != num2[i])
            return 0;
    }
    return 1;    
}


int* findAnagrams(char* s, char* p, int* returnSize){
    
    if(!strlen(s) || !strlen(p) || (strlen(p)>strlen(s))) {
        *returnSize=0;
        return NULL;
    }
    
    int num2[26]={0};
    form_p_arr(p,num2);
    *returnSize=0;
    
    int *ret_arr=(int*)malloc(strlen(s)*sizeof(int));
    memset(ret_arr,0,strlen(s));
    int ret_size=0;
    for(int j=0;j<=strlen(s)-strlen(p);j++){
        if(check_anagram(s+j,strlen(p),num2)){
            ret_arr[ret_size++]=j;
        }
    }
    *returnSize=ret_size;
    return ret_arr;
}

coding problems