Really C++ O(n) 26ms solution using precomputed hashes.


  • 0
    O
    const int MAGICK = 31;
    
    
    // polynomial hash of the first k characters
    // O(k) time, O(1) mem
    int poly_hash(string const& s, int k) {
      int sum = 0;
      for (int i = 0; i < k; ++i) {
        sum *= MAGICK;
        sum += s[i];
      }
      return sum;
    }
    
    // compute hash of every substring of length k
    // O(n) time, O(n - k) mem, n = s.length()
    vector<int> precompute_hashes(string const& s, int k) {
      assert(k <= s.size());
      vector<int> result(s.size() - k + 1);
      int sum = poly_hash(s, k);
      int acc = 1;
      for (int i = 0; i < k - 1; i++) {
        acc *= MAGICK;
      }
    
      // sliding windows of size k starting at i
      for (int i = 0; i + k <= s.size(); ++i) {
        result[i] = sum;
        sum -= s[i] * acc;
        sum *= MAGICK;
        if (i + k < s.size())
          sum += s[i + k];
      }
    
      return result;
    }
    
    // assuming key in map,
    // decrease value of map[key]
    // if value drops to 0, delete key from map
    void decrease_key(unordered_map<int, int>& map, int key) {
      auto it = map.find(key);
      if (--it->second == 0)
        map.erase(it);
    }
    
    
    
    class Solution {
    public:
        // O(n) time, O(n) mem
        vector<int> findSubstring(string s, vector<string> const& words) {
          vector<int> result;
          int n = s.length(), m = words.size();
          if (n == 0 || m == 0)
            return result;
          int k = words[0].length();
          int words_len = k * m;
          if (k == 0 || words_len > n)
            return result;
        
          // O(n)
          auto hashes = precompute_hashes(s, k);
        
          // O(words_len) time
          unordered_map<int, int> word_count;
          for (auto const& word: words) {
            ++word_count[poly_hash(word, word.length())];
          }
          const auto not_found = word_count.end();
        
          // O(k) * O(n / k) * O(1) = O(n)
          for (int i = 0; i < k; ++i) {
            unordered_map<int, int> count;
            int start = i;
            if (start + words_len > n)
              return result;
            for (int j = i; j + k <= n; j += k) {
              auto it = word_count.find(hashes[j]);
              if (it != not_found) {
                // how many words with hashes[j] are left to find
                int to_find = it->second - (++count[hashes[j]]);
                if (to_find > 0)
                  continue;
                if (to_find == 0) {
                  // check if we found a solution
                  // if so, move start to next word
                  if (start + words_len == j + k) {
                    result.push_back(start);
                    decrease_key(count, hashes[start]);
                    start += k;
                  }
                  continue;
                }
                // to_find < 0
                // move start to the position where to_find == 0
                while (hashes[start] != hashes[j]) {
                  decrease_key(count, hashes[start]);
                  start += k;
                }
                decrease_key(count, hashes[j]);
                start += k;
                if (start + words_len > n)
                  break;
                continue;
              }
              start = j + k;
              if (start + words_len > n)
                break;
              count.clear();
            }
        
          }
        
          return result;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.