LeetCode [30] Substring with Concatenation of All Words

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

Example 1:

Input:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input:
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
Output: []

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { vector<int> ret; if(words.size()==0) return ret; unordered_map<string, int> dict, dict1; for(auto w:words) dict[w]++; int ns = s.size(), nw = words[0].size(), c = words.size(); for(int i=0; i<nw; ++i){ int start = i, cnt = 0, p = start; dict1.clear(); while(p+nw<=ns){ string ss = s.substr(p, nw); if(dict.count(ss)==0){ start = p+nw; cnt = 0; p = start; dict1.clear(); }else{ dict1[ss]++; cnt++; while(dict1[ss]>dict[ss]){ dict1[s.substr(start, nw)]--; cnt--; start += nw; } if(cnt==c) ret.push_back(start); p += nw; } } } return ret; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

class Solution { template <typename map> bool map_compare(map const &lhs, map const &rhs) { // No predicate needed because there is operator== for pairs already. return lhs.size() == rhs.size() && std::equal(lhs.begin(), lhs.end(), rhs.begin()); } public: vector<int> findSubstring(string s, vector<string> &words) { vector<int> ret; int sl = s.size(); if(words.size()==0) return ret; int wsz = words[0].size(); map<string, int> dic; for (auto w : words) dic[w]++; for (int i = 0; i < wsz; ++i) { map<string, int> dic1; int l = i, r = l; while (r + wsz - 1 < sl) { string w1 = s.substr(r, wsz); r += wsz; if(dic.count(w1)==0) { dic1.clear(); l = r; continue; } dic1[w1]++; while (dic1[w1] > dic[w1]) { string w2 = s.substr(l, wsz); dic1[w2]--; l += wsz; } if (map_compare(dic, dic1)) { ret.push_back(l); dic1[s.substr(l, wsz)]--; l += wsz; } } } return ret; } };