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: 

  1. S: "barfoothefoobarman"
  2. L: ["foo", "bar"]

You should return the indices: [0,9].(order does not matter).

分析

无

代码

  1. // LeetCode, Substring with Concatenation of All Words
  2. // 时间复杂度O(n*m)，空间复杂度O(m)
  3. class Solution {
  4. public:
  5.     vector<int> findSubstring(string s, vector<string>& dict) {
  6.         size_t wordLength = dict.front().length();
  7.         size_t catLength = wordLength * dict.size();
  8.         vector<int> result;
  10.         if (s.length() < catLength) return result;
  12.         unordered_map<string, int> wordCount;
  14.         for (auto const& word : dict) ++wordCount[word];
  16.         for (auto i = begin(s); i <= prev(end(s), catLength); ++i) {
  17.             unordered_map<string, int> unused(wordCount);
  19.             for (auto j = i; j != next(i, catLength); j += wordLength) {
  20.                 auto pos = unused.find(string(j, next(j, wordLength)));
  22.                 if (pos == unused.end() || pos->second == 0) break;
  24.                 if (--pos->second == 0) unused.erase(pos);
  25.             }
  27.             if (unused.size() == 0) result.push_back(distance(begin(s), i));
  28.         }
  30.         return result;
  31.     }
  32. };

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/simulation/substring-with-concatenation-of-all-words.html