LeetCode Substring with Concatenation of All Words

Description

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

For example, given:
s: “barfoothefoobarman”
words: [“foo”, “bar”]

You should return the indices: [0,9].
(order does not matter).

The original problem is here.

The original code is here.

My Solution

I solve this problem in C++, as below:

/*
*Substring with Concatenation of All Words 
*Author: shuaijiang
*Email: zhaoshuaijiang8@gmail.com
*/
#include<iostream>
#include<vector>
#include<stdlib.h>
using namespace std;

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> result;
        int wordsNum = words.size();
        if(wordsNum <= 0)
            return result;
        int wordLen = words[0].size();
        int strLen  = s.size();
        if(strLen <= 0 || strLen < wordLen)
            return result;
        
        map<string, int> wordMap;
        for(int i=0;i<wordsNum;i++)
            ++ wordMap[words[i]];
        
        int subLen = wordsNum * wordLen; 
        for(int i=0;i<=strLen - subLen;i++){
            map<string, int> myMap(wordMap);
            for(int j=i;j<i+subLen;j+=wordLen){
                string substr = s.substr(j,wordLen);
                if(myMap.find(substr) != myMap.end()){
                    myMap[substr] --;
                    if(myMap[substr] == 0)
                        myMap.erase(substr);
                }                    
                else
                    break;
            }
            if(myMap.size() == 0)
                result.push_back(i);
        }
        return result;
    }
};

Note

In the solution, we need traversal the string. And, map is used to save the dictionary. If a substring is consisted of all the words in the dictionary, we get one answer.