30.substring with concatenation of all words
难度Hard
刷题内容
原题连接
- https://leetcode.com/problems/substring-with-concatenation-of-all-words/
内容描述
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 s that 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 = "wordgoodstudentgoodword",
words = ["word","student"]
Output: []
思路 **- 时间复杂度: O(mlgn)*- 空间复杂度: O(m+n)***
这题可以两个 map 来解决，第一个 map 中存放了 words 中的所有单词和出现的次数，接下来遍历字符串，固定区间的大小为 words 的长度，存入另一个map，两个 map 相等就放入返回数组中
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> ans;
if(!s.length() || !words.size())
return ans;
unordered_map<string,int> m1;
int len = words.size(),wl = words[0].length(),sl = s.length();
for(int i = 0;i < words.size();++i)
m1[words[i]]++;
int count1 = 0,reLen = wl * len,left = 0;
for(int i = 0;i < sl - wl * len + 1;++i)
{
unordered_map<string,int> m2;
for(int j = 0,left = i;j < len;j ++)
{
string temp = s.substr(left,wl);
left += wl;
m2[temp]++;
}
if(m2 == m1)
ans.push_back(i);
}
return ans;
}
};
