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 sthat 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: []
Solution1: HashTable + Brute Force
Time complexity: O((|S| – |W|*l) * |W|*l))
Space complexity: O(|W|*l)
C++
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 |
// Author: Huahua // std::string_view running time: 128 ms, 16 MB // std::string running time: 156 ms, 22.4 MB class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { if (words.empty() || s.empty()) return {}; const int n = words.size(); const int l = words[0].length(); if (n * l > s.length()) return {}; std::string_view ss(s); std::unordered_map<std::string_view, int> expected; for (const string& word : words) ++expected[string_view(word)]; vector<int> ans; for (int i = 0; i <= ss.length() - n * l; ++i) { std::unordered_map<std::string_view, int> seen; int count = 0; for (int j = 0; j < n; ++j) { std::string_view w = ss.substr(i + j * l, l); auto it = expected.find(w); if (it == expected.end()) break; if (++seen[w] > it->second) break; ++count; } if (count == n) ans.push_back(i); } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment