Substring with Concatenation of All Words Problem


Description

LeetCode Problem 30.

You are 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.

Example 1:

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

Example 2:

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

Example 3:

1
2
Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]

Constraints:

  • 1 <= s.length <= 10^4
  • s consists of lower-case English letters.
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 30
  • words[i] consists of lower-case English letters.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector findSubstring(string s, vector& words) {
        unordered_map<string, int> counts;
        for (string word : words)
            counts[word]++;
        int n = s.length(), num = words.size(), len = words[0].length();
        vector indexes;
        for (int i = 0; i < n - num * len + 1; i++) {
            unordered_map<string, int> seen;
            int j = 0;
            for (; j < num; j++) {
                string word = s.substr(i + j * len, len);
                if (counts.find(word) != counts.end()) {
                    seen[word]++;
                    if (seen[word] > counts[word])
                        break;
                }
                else break;
            }
            if (j == num) indexes.push_back(i);
        }
        return indexes;
    }
};




Related Posts

Longest Consecutive Sequence Problem

LeetCode 128. Given an unsorted array of integers nums, return...

Set Matrix Zeroes Problem

LeetCode 73. Given an m x n integer matrix matrix,...

Minimum Window Substring Problem

LeetCode 76. Given two strings s and t of lengths...

Search in Rotated Sorted Array Problem

LeetCode 36. Determine if a 9 x 9 Sudoku board...

Integer to Roman Problem

LeetCode 12. Given an integer, convert it to a roman...