Leetcode 30 Solution

Leetcode Question Link

https://leetcode.com/problems/substring-with-concatenation-of-all-words

Thinking Process

First of all, an important and straightforward property is that a concatenated string’s size is N * K, if N is the size of words, and K is the length of each word.

Based on that, we can just find all the substrings in s with a length of N * K, and check to see if it is a concatenated string.

So the question now becomes how to check if a string is a concatenated string. This is basically to count the words from the concatenated string, and make sure these words match the given words. How do we do that? We keep a word count map for each of them. And if anytime, the word count map of the concatenated string has a count greater than the words word count map, it means this is not a concatenated string. Otherwise, it is one.

Applying the above algorithm for all the length N * K substrings in s solves the challenge.

Time & Space Complexity

Assuming M is the size of s, N is the size of words, and K is the length of each word:

• Time complexity: O((M - N * K) * N * K)
• Space complexity: O(M + N)

Solution

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;

        if (s.size() == 0 || words.size() == 0)
            return res;

        int n = words.size();
        int m = words[0].size();

        unordered_map<string, int> m1;
        for (auto& word : words)
            m1[word]++;

        for (int i = 0; i <= (int)s.size() - m * n; i++)
        {
            unordered_map<string, int> m2;

            int j;
            for (j = 0; j < n; j++)
            {
                auto word = s.substr(i + j * m, m);
                if (m1.find(word) == m1.end() || m2[word] >= m1[word])
                    break;
                m2[word]++;
            }

            if (j == n)
                res.push_back(i);
        }

        return res;
    }
};