## Substring with Concatenation of All Words

You are given a string,

**S**, and a list of words,**L**, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:

**S**:`"barfoothefoobarman"`

**L**:`["foo", "bar"]`

You should return the indices:

(order does not matter).

`[0,9]`

.(order does not matter).

### Analysis:

Try to think this problem straightforward:

Say in L there are m strings with length n.

**What string is required to match in S? A length of m*n string start with each position in S.**

**What is a match? In the m*n long string, every string in L appear only once.**

**So the algorithm is:**

**Scan every m*n long string start from each position in S, see if all the strings in L have been appeared only once using Map data structure. If so, store the starting position.**

Yes, do not consider any DP or DFS solutions, just using the hash map and loop.

### Code(C++):

class Solution { public: vector<int> findSubstring(string S, vector<string> &L) { // Start typing your C/C++ solution below // DO NOT write int main() function vector<int> res; int num = L.size(); int len = L[0].size(); if (num==0){return res;} map<string,int> mp; for (int i=0;i<num;i++){mp[L[i]]++;} int i=0; while ((i+num*len-1)<S.size()){ map<string,int> mp2; int j=0; while (j<num){ string subs = S.substr(i+j*len,len); if (mp.find(subs)==mp.end()){ break; }else{ mp2[subs]++; if (mp2[subs]>mp[subs]){ break; } j++; } } if (j==num){res.push_back(i);} i++; } return res; } };

### Code(Python):

class Solution: # @param S, a string # @param L, a list of string # @return a list of integer def findSubstring(self, S, L): res = [] # result list num = len(L) # length of the str list ls = len(S) if num == 0: return [] str_len = len(L[0]) # length of each str #create the map: count the occurrance of each string #Note that set(L) is used to reduce the time, otherwise will not pass the large test map_str = dict((x,L.count(x)) for x in set(L)) i = 0 while i + num * str_len - 1 < ls: map_str2 = {} j = 0 while j < num: subs = S[i + j * str_len:i + j * str_len + str_len ] if not subs in map_str: break else: # Note that dict.get(key, default_val) is used to handel the case that key NOT exist map_str2[subs] = map_str2.get(subs, 0) + 1 if map_str2[subs]>map_str[subs]: break j = j + 1 if j == num: res.append(i) i = i + 1 return res

Is there another example? I mean apart from barfoothefoobarman

ReplyDeleteThanks

ReplyDelete