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: [0,9].
(order does not matter).

C++:
01 class Solution {
02 public:
03     vector<int> findSubstring(string S, vector<string> &L) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function
06         int i=0;
07         vector<int> result;
08         int n=L.size();
09         if(n==0)    return result;
10         int m=L[0].size();
11         int r=S.size();
12         vector<int> A;
13         map<string, int> B;
14         for(int j=0;j<n;j++)
15         {
16             if(B.find(L[j])==B.end())
17             {
18                 A.push_back(1);
19                 B[L[j]]=i++;
20             }
21             else
22             {
23                 A[B[L[j]]]++;
24             }
25         }
26         vector<int> C;
27         for(int j=0;j<rm+1;j++)
28         {
29             string tmp=S.substr(j,m);
30             if(B.find(tmp)==B.end())
31             {
32                 C.push_back(1);
33             }
34             else
35             {
36                 C.push_back(B[tmp]);
37             }
38         }
39         for(int p=0;p<rm+1;p++)
40         {
41             int cnt=0;
42             vector<int> D(A);
43             for(int q=p;q<rm+1;q=q+m)
44             {
45                 if(C[q]==-1)    break;
46                 int t=C[q];
47                 if(D[t]==0)     break;
48                 D[t];
49                 cnt++;
50             }
51             if(cnt==n)
52             {
53                 result.push_back(p);
54             }
55         }
56         return result;
57     }
58 };
Advertisements
This entry was posted in Array and linked list, Hashtable and Map, String. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s