Algorithm
Problem Name: 30. Substring with Concatenation of All Words
Problem Link: https://leetcode.com/problems/substring-with-concatenation-of-all-words/
You are given a string s and an array of strings words. All the strings of words are of the same length.
A concatenated substring in s is a substring that contains all the strings of any permutation of words concatenated.
- For example, if
words = ["ab","cd","ef"], then"abcdef","abefcd","cdabef","cdefab","efabcd", and"efcdab"are all concatenated strings."acdbef"is not a concatenated substring because it is not the concatenation of any permutation ofwords.
Return the starting indices of all the concatenated substrings in s. You can return the answer in any order.
Example 1:
Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9] Explanation: Since words.length == 2 and words[i].length == 3, the concatenated substring has to be of length 6. The substring starting at 0 is "barfoo". It is the concatenation of ["bar","foo"] which is a permutation of words. The substring starting at 9 is "foobar". It is the concatenation of ["foo","bar"] which is a permutation of words. The output order does not matter. Returning [9,0] is fine too.
Example 2:
Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] Output: [] Explanation: Since words.length == 4 and words[i].length == 4, the concatenated substring has to be of length 16. There is no substring of length 16 is s that is equal to the concatenation of any permutation of words. We return an empty array.
Example 3:
Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] Output: [6,9,12] Explanation: Since words.length == 3 and words[i].length == 3, the concatenated substring has to be of length 9. The substring starting at 6 is "foobarthe". It is the concatenation of ["foo","bar","the"] which is a permutation of words. The substring starting at 9 is "barthefoo". It is the concatenation of ["bar","the","foo"] which is a permutation of words. The substring starting at 12 is "thefoobar". It is the concatenation of ["the","foo","bar"] which is a permutation of words.
Constraints:
1 <= s.length <= 1041 <= words.length <= 50001 <= words[i].length <= 30sandwords[i]consist of lowercase English letters.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
typedef struct item_s {
char *word;
int idx;
struct item_s *next;
} item_t;
typedef struct {
item_t *p;
int n;
} buff_t;
#define HF 1021
unsigned int hash_code(const char *s, int len) {
unsigned int hc = 5381;
char c;
while (len -- > 0) {
hc = hc * 33 + s[len];
}
return hc % HF;
}
item_t *lookup(item_t **ht, unsigned int hc, const char *w, int len) {
item_t *p = ht[hc];
while (p) {
if (!strncmp(p->word, w, len)) {
return p;
}
p = p->next;
}
return NULL;
}
int* findSubstring(char* s, char** words, int wordsSize, int* returnSize) {
item_t *ht[HF] = { 0 }, **sp, *p;
int *counts, *counts2, total, i;
char *w;
unsigned int hc;
int total_len, word_len;
int left, mid, right;
int *results;
if (wordsSize == 0) return NULL;
buff_t buff = { 0 };
buff.p = malloc(wordsSize * sizeof(item_t));
//assert(buff->p);
counts = calloc(wordsSize * 2, sizeof(int));
//assert(counts);
counts2 = &counts[wordsSize];
total = 0;
word_len = strlen(words[0]);
total_len = strlen(s);
sp = malloc(total_len * sizeof(item_t *));
//assert(sp);
results = malloc(total_len * sizeof(int));
//assert(results);
*returnSize = 0;
for (i = 0; i < wordsSize; i ++) {
w = words[i];
hc = hash_code(w, word_len);
p = lookup(ht, hc, w, word_len);
if (p) {
counts[p->idx] ++;
} else {
p = &buff.p[buff.n];
p->idx = buff.n ++;
p->word = w;
p->next = ht[hc];
ht[hc] = p;
counts[p->idx] = 1;
}
}
left = mid = right = 0;
while (right < = total_len - word_len) {
w = &s[right];
hc = hash_code(w, word_len);
p = lookup(ht, hc, w, word_len);
if (!p) {
total = 0;
memset(counts2, 0, buff.n * sizeof(int)); // reset all counts
left ++; // shift one character from left
mid = left;
right = left; // reset right
} else {
sp[right] = p;
i = p->idx;
counts2[i] ++;
total ++;
while (counts2[i] > counts[i]) {
p = sp[mid];
mid += word_len; // push out a word
counts2[p->idx] --;
total --;
}
if (total == wordsSize) { // all are found
results[*returnSize] = mid;
(*returnSize) ++;
total = 0;
memset(counts2, 0, buff.n * sizeof(int)); // reset all counts
left = mid + 1;
mid = left;
right = left;
} else {
right += word_len;
}
}
}
free(buff.p);
free(counts);
free(sp);
return results;
}
Input
s = "barfoothefoobarman", words = ["foo","bar"]
Output
[0,9]
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List findSubstring(String s, String[] words) {
int numberOfWords = words.length;
int singleWordLength = words[0].length();
int totalSubstringLength = singleWordLength * numberOfWords;
Map < String, Integer> wordCount = new HashMap<>();
for (String word : words) {
wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
}
List < Integer> result = new ArrayList<>();
for (int i = 0; i < singleWordLength; i++) {
slidingWindow(i, s, result, singleWordLength, totalSubstringLength, wordCount, numberOfWords);
}
return result;
}
private void slidingWindow(int left, String s, List < Integer> answer, int singleWordLength,
int totalSubstringLength, Map wordCount, int numberOfWords) {
Map wordsFound = new HashMap<>();
int wordsUsed = 0;
boolean excessWord = false;
int n = s.length();
for (int right = left; right < = n - singleWordLength; right += singleWordLength) {
String currSubstring = s.substring(right, right + singleWordLength);
if (!wordCount.containsKey(currSubstring)) {
wordsFound.clear();
wordsUsed = 0;
excessWord = false;
left = right + singleWordLength;
} else {
while (right - left == totalSubstringLength || excessWord) {
String leftmostWord = s.substring(left, left + singleWordLength);
left += singleWordLength;
wordsFound.put(leftmostWord, wordsFound.get(leftmostWord) - 1);
if (wordsFound.get(leftmostWord) >= wordCount.get(leftmostWord)) {
excessWord = false;
} else {
wordsUsed--;
}
}
wordsFound.put(currSubstring, wordsFound.getOrDefault(currSubstring, 0) + 1);
if (wordsFound.get(currSubstring) < = wordCount.get(currSubstring)) {
wordsUsed++;
} else {
excessWord = true;
}
if (wordsUsed == numberOfWords && !excessWord) {
answer.add(left);
}
}
}
}
}
Input
s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output
[]
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const findSubstring = function(s, words) {
if (words == null || words.length === 0 || !s) return []
const wh = {}
const slen = s.length
const wl = words[0].length
const len = words[0].length * words.length
words.forEach(el => {
if (wh[el]) wh[el]++
else wh[el] = 1
})
const res = []
for (let i = 0; i < slen - len + 1; i++) {
if (chk(wh, s.slice(i, i + len), wl, words.length)) res.push(i)
}
return res
}
function chk(hash, str, wl, num) {
const oh = {}
for (let i = 0; i < num; i++) {
let tmp = str.slice(i * wl, i * wl + wl)
if (oh[tmp]) oh[tmp]++
else oh[tmp] = 1
}
const keys = Object.keys(hash)
for (let i = 0; i < keys.length; i++) {
if (oh[keys[i]] !== hash[keys[i]]) return false
}
return true
}
Input
s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output
[6,9,12]
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findSubstring(self, s, words):
if not s or not words: return []
cnt, l_words, l_word, cnt_words, res = collections.Counter(words), len(words[0]) * len(words), len(words[0]), len(words), []
for i in range(len(s) - l_words + 1):
cur, j = dict(cnt), i
for _ in range(cnt_words):
w = s[j:j + l_word]
if w in cur:
if cur[w] == 1: cur.pop(w)
else: cur[w] -= 1
else: break
j += l_word
if not cur: res += i,
return res
Input
s = "barfoothefoobarman", words = ["foo","bar"]
Output
[0,9]
#5 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _030_SubstringWithConcatenationOfAllWords
{
public IList < int> FindSubstring(string s, string[] words)
{
var result = new List<int>();
var wordsLenght = words.Length;
var sLenght = s.Length;
if (sLenght == 0 || wordsLenght == 0) { return result; }
var wordLenght = words[0].Length;
var concatLenght = wordsLenght * wordLenght;
if (concatLenght > sLenght) { return result; }
var wordsMap = new Dictionary < string, int>();
foreach (var word in words)
{
if (wordsMap.ContainsKey(word))
{
wordsMap[word]++;
}
else
{
wordsMap[word] = 1;
}
}
IDictionary < string, int> used;
int i, j, count;
var subString = string.Empty;
bool allUsed = false;
for (i = 0; i < = sLenght - concatLenght; i++)
{
used = new Dictionary(wordsMap);
for (j = i; j < = sLenght - wordLenght; j += wordLenght)
{
subString = s.Substring(j, wordLenght);
if (used.TryGetValue(subString, out count))
{
if (count == 0) { break; }
used[subString]--;
}
else
{
break;
}
}
allUsed = true;
foreach (var pair in used)
{
if (pair.Value > 0) { allUsed = false; break; }
}
if (allUsed) { result.Add(i); }
}
return result;
}
}
}
Input
s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output
[]