# 30. 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.

Example 1:

Input:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input:
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
Output: []

# Solution

Approach 1: Scan the string s to match each word and the total number of the words.

Approach 2: (Time Limit Exceeded) First get all permutations of words, and then scan the string s to match each permutation.

# Code (Python)

Approach 1:

import collections

class Solution:
    def findSubstring(self, s, words):
        # http://www.cnblogs.com/zuoyuan/p/3779978.html
        # time: O(len(S) * num_of_words)
        result = []
        numWords = len(words)
        lenWords = len(words[0])
        # word_table remembers words -- will use word_table as a reference
        word_table = collections.defaultdict(int)
        for word in words:
            word_table[word] += 1
        # for each index of s, check if it's valid
        for i in range(len(s) - numWords * lenWords + 1):
            table = collections.defaultdict(int)
            wordcount = 0
            while wordcount < len(words):
                new_word = s[i + lenWords * wordcount : i + lenWords * (wordcount + 1)]
                # violates "without any intervening characters"
                if new_word not in word_table:
                    break
                table[new_word] += 1
                # violates "exactly once"
                if table[new_word] > word_table[new_word]:
                    break
                wordcount += 1
            if wordcount == len(words):
                result.append(i)
        return result

Approach 2:

# Code (C++)

Approach 1:

// Scan the string s to match each word and the total number of the words.
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        int wordsSize = words.size();
        if (wordsSize == 0 || s.size() == 0)
            return res;
        int wordLen = words[0].size();
        unordered_map<string,int> wordsMap;
        for (int i = 0; i < words.size(); ++i)
        {
            wordsMap[words[i]]++;
        }
        for (int i = 0; i + wordLen * wordsSize <= s.size(); ++i)
        {
            unordered_map<string,int> sMap;
            int j = 0;
            for (; j <= wordsSize; ++j)
            {
                string curr = s.substr(i + j * wordLen, wordLen);
                if (wordsMap.find(curr) == wordsMap.end())
                    break;
                sMap[curr]++;
                if (sMap[curr] > wordsMap[curr])
                    break;
            }
            if (j == wordsSize)
                res.push_back(i);
        }
        return res;
    }
};

Approach 2:

// Time Limit Exceeded.
// First get all permutations of words, and then scan the string s to match each permutation.
class Solution {
private:
    unordered_set<string> p;
    void getAllPermutations(vector<string>& words, int head) {
        if (head == words.size() - 1)
        {
            ostringstream oss;
            for (int i = 0; i < words.size(); ++i)
            {
                oss << words[i];
            }
            p.insert(oss.str());
            return;
        }
        getAllPermutations(words, head+1);
        unordered_set<string> visited;
        for (int i = head + 1; i < words.size(); ++i)
        {
            if (words[head] == words[i] ||
               visited.find(words[i]) != visited.end())
                continue;
            visited.insert(words[i]);
            std::swap(words[head], words[i]);
            getAllPermutations(words, head+1);
            std::swap(words[head], words[i]);
        }
    }
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        int wordsSize = words.size();
        if (wordsSize == 0 || s.size() == 0)
            return res;
        int wordLen = words[0].size();
        getAllPermutations(words, 0);
        for (int i = 0; i + wordLen * wordsSize <= s.size(); ++i)
        {
            if (p.find(s.substr(i, wordLen * wordsSize)) != p.end())
                res.push_back(i);
        }
        return res;
    }
};