Problem
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 = "wordgoodstudentgoodword",
words = ["word","student"]
Output: []
Solution
/**
* @param {string} s
* @param {string[]} words
* @return {number[]}
*/
var findSubstring = function(s, words) {
var sLen = s.length;
var wLen = words.length;
var wordLen = (words[0] || '').length;
if (!sLen || !wLen || !wordLen) return [];
var count = 0;
var tmp = '';
var map1 = {};
var map2 = {};
var res = [];
for (var i = 0; i < wLen; i++) {
map1[words[i]] = (map1[words[i]] || 0) + 1;
}
out: for (var j = 0; j <= sLen - (wLen * wordLen); j++) {
map2 = {};
count = 0;
while (count < wLen) {
tmp = s.substr(j + (count * wordLen), wordLen);
if (map1[tmp] === undefined || map1[tmp] === map2[tmp]) continue out;
map2[tmp] = (map2[tmp] || 0) + 1;
count++;
}
res.push(j);
}
return res;
};
Explain:
nope.
Complexity:
- Time complexity : O(m*n).
- Space complexity : O(m).