You are given a string s
and an array of strings words
of the same length. Return all starting indices of substring(s) in s
that is a concatenation of each word in words
exactly once, in any order, and without any intervening characters.
You can return the answer in any order.
Example 1:
Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9] Explanation: Substrings starting at index 0 and 9 are "barfoo" 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: []
Example 3:
Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] Output: [6,9,12]
Constraints:
1 <= s.length <= 104
s
consists of lower-case English letters.1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i]
consists of lower-case English letters.
Solution: Hashtable + Brute Force
Try every index and use a hashtable to check coverage.
Time complexity: O(n*m*l)
Space complexity: O(m*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 |
// Author: Huahua class Solution { public: vector<int> findSubstring(string_view s, vector<string>& words) { const int n = s.length(); const int m = words.size(); const int l = words[0].size(); if (m * l > n) return {}; unordered_map<string_view, int> freq; for (const string& word : words) ++freq[word]; vector<int> ans; for (int i = 0; i <= n - m * l; ++i) { unordered_map<string_view, int> seen; int count = 0; for (int k = 0; k < m; ++k) { string_view t = s.substr(i + k * l, l); auto it = freq.find(t); if (it == end(freq)) break; if (++seen[t] > it->second) break; ++count; } if (count == m) ans.push_back(i); } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment