Leetcode Substring with Concatenation of All Words problem solution

In this Leetcode Substring with Concatenation of All Words problem solution, we have given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters. You can return the answer in any order.

Problem solution in Python.

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if(len(words)==0):
            return []
        N = len(words[0])
        if(len(s) < N*len(words)):
            return []
        i=0;location=[]
        def recursion(firstWord,words,s,location,N):
            if not words:
                return location
            if(firstWord in set(words)):
                words.remove(firstWord)
                pos = recursion(s[location+N:location+2*N],words,s,location+N,N)
                if(pos == -1):
                    return -1
                else:
                    return location
            else:
                return -1
        while(i<len(s)):
            firstWord = s[i:i+N]
        
            pos = recursion(firstWord,words[:],s,i,N)
            
            if(pos!=-1):
                location.append(pos)
            i+=1
        return location

Problem solution in Java.

public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if(words.length == 0 || words[0].length() == 0 || s.length() == 0) return res;
        int wordLen = words[0].length();
        int wordNum = words.length;
        int windowSize = wordLen * wordNum;
        Map<String,Integer> map = new HashMap<>();
        
        for(String eachWord : words) {
            map.put(eachWord,map.getOrDefault(eachWord,0) + 1);
        }
       
        for(int i = 0;i + windowSize - 1 < s.length();i++) {
            String lastWord = s.substring(i + windowSize - wordLen,i + windowSize);
            if(map.containsKey(lastWord)) {
                boolean bre = false;
                Map<String,Integer> currMap = new HashMap<>(map);
                for(int j = i;j < i + windowSize;j += wordLen) {
                    String currWord = s.substring(j,j + wordLen);
                    currMap.put(currWord,currMap.getOrDefault(currWord,0) - 1);
                    if(currMap.get(currWord) < 0) {
                        bre = true;
                        break;
                    }
                }
                if(!bre)res.add(i);
            }
        }
        return res;
    }

Problem solution in C++.

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int>ans;
        if(!s.size() || !words.size())
            return ans;
        unordered_map<string,int>mp1;
        unordered_map<string,int>mp2;
        for(auto word:words)
        {
            mp1[word]++;
        }
        int len = words.size();
        int tl = words[0].size()*len;
        int sl = words[0].size();
        int i = 0;
        if(tl>s.size())
            return ans;
        while(i<=s.size()-tl)
        {
            
            string sub = s.substr(i,tl);
            int k = 0;
            int n = 0;
            while(k<words.size())
            {
                string temp = sub.substr(n,sl);
                mp2[temp]++;
                n += sl;
                k++;
            }
            if(mp2 == mp1)
                ans.push_back(i);
            mp2.clear();
            i++;
        }
        return ans;
    }
};

Problem solution in C.

typedef struct entry{
    char* word;
    int occurred;
    int occurrence;
    struct entry* next;
    
} dic_entry;

dic_entry* add_entry(dic_entry* dic, char* word)
{
    dic_entry* new_entry = (dic_entry*)malloc(sizeof(dic_entry));
    new_entry->word = (char*)malloc(sizeof(char)*(strlen(word)+1));
    strcpy(new_entry->word, word);
    new_entry->occurred = 0;
    new_entry->occurrence = 1;
    new_entry->next = NULL;
    dic_entry* head = dic;
    
    if(dic == NULL)
    {
        head = new_entry;
    }
    else
    {
        while(dic->next)
        {
            dic = dic->next;
        }
        
        dic->next = new_entry;
    }
    return head;
}

dic_entry* find_entry(dic_entry* dic, char* word, int len)
{
    
    dic_entry* head = dic;
    while(head)
    {
        if(!strncmp(head->word, word, len))
        {
            return head;
        }
        head = head->next;
    }
    return NULL;
}

void reset(dic_entry* dic)
{
    dic_entry* head = dic;
    
    while(head)
    {
        head->occurred = 0;
        head = head->next;
    }
}

void free_dic(dic_entry* dic)
{
    dic_entry* head = dic;
    dic_entry* temp;
    
    while(head)
    {
        free(head->word);
        temp = head;
        head = head->next;
        free(temp);
    }
}


int* findSubstring(char * s, char ** words, int wordsSize, int* returnSize){
    
    int* result = (int*)malloc(sizeof(int));
    int resultCount = 0;
    dic_entry* dic = NULL;
    dic_entry* temp;
    int j;
    int string_len = (int)strlen(s);
    
    if (wordsSize == 0)
    {
        *returnSize = 0;
        return result;
    }
    
    int word_len = strlen(words[0]);
    
    for(int i = 0; i < wordsSize; i++)
    {
        
        temp = find_entry(dic, words[i], word_len);
        
        if(temp != NULL)
        {
            temp->occurrence++;
        }
        else
        {
            dic = add_entry(dic, words[i]);
        }
        
    }
    
    for(int i = 0; i <= string_len - wordsSize*word_len; i++)
    {
        for(j = 0; j < wordsSize; j++)
        {
            temp = find_entry(dic, s+j*word_len+i, word_len);
            if(temp)
            {
                temp->occurred++;
                if (temp->occurred > temp->occurrence)
                    break;
            }
            else
            {
                break;
            }
        }
        
        if(j == wordsSize)
        {
            result[resultCount++] = i;
            result = (int*)realloc(result, sizeof(int)*(resultCount+1));
        }
        
        reset(dic);
    }
    
    
    free_dic(dic);
    *returnSize = resultCount;
    return result;
    
}