Leetcode: Substring with Concatenation of All Words (hash table)(string)solution

PROBLEM:
https://leetcode.com/problems/substring-with-concatenation-of-all-words/


This problem is designed for using hash table. Other kinds of smarter methods exist, but it will take a long time to figure it out, at least for me. So here I focus on the general method, hash table.

the method using here is very similar to following problem in this post:

Leetcode: Valid Anagram (hash table)(sort)

At first, we build a map for the words with repeating frequency, the second value of the map is the occurrence frequency:

see the following two methods to build the frequency map:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

1.

              map<string, int> w;

              for (int i = 0; i<words.size(); i++){

                     //if exist already

                     if (w.find(words[i]) != w.end()){

                           w[words[i]]++;

                     }

                     else w[words[i]] = 1;

              }

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

2.

              for (int i = 0; i<words.size(); i++){

                    w[words[i]]++;

               }

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Apparently, the second method is better. We don't need to identify whether the item we want to add exist in map or not. Why? Please refer to reference somewhere. 

The second step is to check the string s from left to right one by one. What i'm using here is to minus the frequency in map w, until all is 0, which means we find one. Or if the frequency value become negative or we can't find the item in map w, break the loop and continue the next one. ....

////////////////////////////////////////////////////////////////////////////

class Solution {

public:

       vector<int> findSubstring(string s, vector<string>& words) {

              int n = words[0].size(), m = words.size(), len = s.size();

              map<string, int> w;

              vector<int> res;

              //build map for words, duplication should be considered!

              for (int i = 0; i<words.size(); i++){

                     w[words[i]]++;

              }

              //search in the dictionary, s.

              int th1 = len - m*n + 1, th2 = (m - 1)*n;

              for (int i = 0; i<th1; i++){

                     map<string, int> wTmp = w;

                     int j = i;

                     while (j - i <= th2 && j<len){

                           string tmp;

                           tmp.assign(s, j, n);

                           if (w.find(tmp) == w.end()) break;

                           else wTmp[tmp]--;

                           //check negative

                           if (wTmp[tmp]<0)break;

                           //check success or not

                           if (j - i == th2) {

                                  res.push_back(i);

                                  break;

                           }

                           j += n;

                     }

              }

              return res;

       }

};