Substring With Concatenation of All Words Problem: 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 :
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.
Table of Contents
Substring With Concatenation of All Words Problem Solution
Problem Solution In Python
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
if(len(words)==0):
return []
N = len(words[0])
if(len(s) < N*len(words)):
return []
i=0;location=[]
def recursion(firstWord,words,s,location,N):
if not words:
return location
if(firstWord in set(words)):
words.remove(firstWord)
pos = recursion(s[location+N:location+2*N],words,s,location+N,N)
if(pos == -1):
return -1
else:
return location
else:
return -1
while(i<len(s)):
firstWord = s[i:i+N]
pos = recursion(firstWord,words[:],s,i,N)
if(pos!=-1):
location.append(pos)
i+=1
return location
Problem Solution In Java
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<>();
if(words.length == 0 || words[0].length() == 0 || s.length() == 0) return res;
int wordLen = words[0].length();
int wordNum = words.length;
int windowSize = wordLen * wordNum;
Map<String,Integer> map = new HashMap<>();
for(String eachWord : words) {
map.put(eachWord,map.getOrDefault(eachWord,0) + 1);
}
for(int i = 0;i + windowSize - 1 < s.length();i++) {
String lastWord = s.substring(i + windowSize - wordLen,i + windowSize);
if(map.containsKey(lastWord)) {
boolean bre = false;
Map<String,Integer> currMap = new HashMap<>(map);
for(int j = i;j < i + windowSize;j += wordLen) {
String currWord = s.substring(j,j + wordLen);
currMap.put(currWord,currMap.getOrDefault(currWord,0) - 1);
if(currMap.get(currWord) < 0) {
bre = true;
break;
}
}
if(!bre)res.add(i);
}
}
return res;
}
Problem Solution In C++
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int>ans;
if(!s.size() || !words.size())
return ans;
unordered_map<string,int>mp1;
unordered_map<string,int>mp2;
for(auto word:words)
{
mp1[word]++;
}
int len = words.size();
int tl = words[0].size()*len;
int sl = words[0].size();
int i = 0;
if(tl>s.size())
return ans;
while(i<=s.size()-tl)
{
string sub = s.substr(i,tl);
int k = 0;
int n = 0;
while(k<words.size())
{
string temp = sub.substr(n,sl);
mp2[temp]++;
n += sl;
k++;
}
if(mp2 == mp1)
ans.push_back(i);
mp2.clear();
i++;
}
return ans;
}
};
Problem Solution In C
typedef struct entry{
char* word;
int occurred;
int occurrence;
struct entry* next;
} dic_entry;
dic_entry* add_entry(dic_entry* dic, char* word)
{
dic_entry* new_entry = (dic_entry*)malloc(sizeof(dic_entry));
new_entry->word = (char*)malloc(sizeof(char)*(strlen(word)+1));
strcpy(new_entry->word, word);
new_entry->occurred = 0;
new_entry->occurrence = 1;
new_entry->next = NULL;
dic_entry* head = dic;
if(dic == NULL)
{
head = new_entry;
}
else
{
while(dic->next)
{
dic = dic->next;
}
dic->next = new_entry;
}
return head;
}
dic_entry* find_entry(dic_entry* dic, char* word, int len)
{
dic_entry* head = dic;
while(head)
{
if(!strncmp(head->word, word, len))
{
return head;
}
head = head->next;
}
return NULL;
}
void reset(dic_entry* dic)
{
dic_entry* head = dic;
while(head)
{
head->occurred = 0;
head = head->next;
}
}
void free_dic(dic_entry* dic)
{
dic_entry* head = dic;
dic_entry* temp;
while(head)
{
free(head->word);
temp = head;
head = head->next;
free(temp);
}
}
int* findSubstring(char * s, char ** words, int wordsSize, int* returnSize){
int* result = (int*)malloc(sizeof(int));
int resultCount = 0;
dic_entry* dic = NULL;
dic_entry* temp;
int j;
int string_len = (int)strlen(s);
if (wordsSize == 0)
{
*returnSize = 0;
return result;
}
int word_len = strlen(words[0]);
for(int i = 0; i < wordsSize; i++)
{
temp = find_entry(dic, words[i], word_len);
if(temp != NULL)
{
temp->occurrence++;
}
else
{
dic = add_entry(dic, words[i]);
}
}
for(int i = 0; i <= string_len - wordsSize*word_len; i++)
{
for(j = 0; j < wordsSize; j++)
{
temp = find_entry(dic, s+j*word_len+i, word_len);
if(temp)
{
temp->occurred++;
if (temp->occurred > temp->occurrence)
break;
}
else
{
break;
}
}
if(j == wordsSize)
{
result[resultCount++] = i;
result = (int*)realloc(result, sizeof(int)*(resultCount+1));
}
reset(dic);
}
free_dic(dic);
*returnSize = resultCount;
return result;
}