LeetCode

Substring with Concatenation of All Words

2014.2.27 00:46

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).

Solution:

　　My solution to this problem is basically brute-force, starting from every position and check if a complete concatenation is possible.

　　<unordered_map> will provide efficient hashing.

　　Total time complexity is O(n^3). Space complexity is O(n).

Accepted code:

  1 #include <string>
  2 #include <unordered_map>
  3 #include <vector>
  4 using namespace std;
  5 
  6 class Solution {
  7 public:
  8     vector<int> findSubstring(string S, vector<string> &L) {
  9         vector<int> result_set;
 10         vector<int> vi;
 11         vector<int> vic;
 12         unordered_map<string, int> um;
 13         unordered_map<string, int>::iterator uit;
 14         int wl;
 15         int nc;
 16         int n = (int)L.size();
 17         int slen = (int)S.length();
 18         
 19         if (slen == 0 || n == 0) {
 20             return result_set;
 21         }
 22         wl = (int)L[0].length();
 23         if (wl == 0) {
 24             return result_set;
 25         }
 26         if (slen < n * wl) {
 27             return result_set;
 28         }
 29         
 30         um.clear();
 31         vi.clear();
 32         nc = 0;
 33         
 34         int i, j;
 35         for (i = 0; i < n; ++i) {
 36             uit = um.find(L[i]);
 37             if (uit == um.end()) {
 38                 um[L[i]] = nc;
 39                 vi.push_back(1);
 40                 ++nc;
 41             } else {
 42                 ++vi[um[L[i]]];
 43             }
 44         }
 45         vic.resize(nc);
 46         
 47         int cc, ll, rr;
 48         int idx;
 49         string str;
 50         
 51         for (i = 0; i < wl; ++i) {
 52             for (j = 0; j < nc; ++j) {
 53                 vic[j] = vi[j];
 54             }
 55             cc = 0;
 56             
 57             ll = i;
 58             rr = ll;
 59             while (rr + wl <= slen) {
 60                 str = S.substr(rr, wl);
 61                 uit = um.find(str);
 62                 if (uit != um.end()) {
 63                     idx = uit->second;
 64                     if (vic[idx] == 0) {
 65                         while (true) {
 66                             str = S.substr(ll, wl);
 67                             if (um[str] != idx) {
 68                                 ll += wl;
 69                                 ++vic[um[str]];
 70                                 --cc;
 71                             } else {
 72                                 ll += wl;
 73                                 ++vic[um[str]];
 74                                 --cc;
 75                                 break;
 76                             }
 77                         }
 78                     } else {
 79                         --vic[idx];
 80                         ++cc;
 81                         rr += wl;
 82                     }
 83                 } else {
 84                     ll = rr + wl;
 85                     for (j = 0; j < nc; ++j) {
 86                         vic[j] = vi[j];
 87                     }
 88                     rr = ll;
 89                     cc = 0;
 90                 }
 91                 if (cc == n) {
 92                     result_set.push_back(ll);
 93                     str = S.substr(ll, wl);
 94                     idx = um[str];
 95                     ++vic[idx];
 96                     --cc;
 97                     ll += wl;
 98                 }
 99             }
100         }
101         vic.clear();
102         
103         return result_set;
104     }
105 };