LeetCode Substring with Concatenation of All Words


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
using namespace std;

class Solution {
    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)
            if(myMap.size() == 0)
        return result;


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.