给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
- 例如，如果
words = ["ab","cd","ef"]， 那么"abcdef"，"abefcd"，"cdabef"，"cdefab"，"efabcd"， 和"efcdab"都是串联子串。"acdbef"不是串联子串，因为他不是任何words排列的连接。
返回所有串联字串在 s 中的开始索引。你可以以 任意顺序 返回答案。
示例 1：
输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。
示例 2：
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。
示例 3：
输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] 输出：[6,9,12] 解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。 子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。 子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。 子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。
提示：
1 <= s.length <= 1041 <= words.length <= 50001 <= words[i].length <= 30words[i]和s由小写英文字母组成
方法一：哈希表 + 滑动窗口
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
cnt = Counter(words)
sublen = len(words[0])
n, m = len(s), len(words)
ans = []
for i in range(sublen):
cnt1 = Counter()
l = r = i
t = 0
while r + sublen <= n:
w = s[r : r + sublen]
r += sublen
if w not in cnt:
l = r
cnt1.clear()
t = 0
continue
cnt1[w] += 1
t += 1
while cnt1[w] > cnt[w]:
remove = s[l : l + sublen]
l += sublen
cnt1[remove] -= 1
t -= 1
if m == t:
ans.append(l)
return ansclass Solution {
public List<Integer> findSubstring(String s, String[] words) {
Map<String, Integer> cnt = new HashMap<>();
for (String w : words) {
cnt.put(w, cnt.getOrDefault(w, 0) + 1);
}
int subLen = words[0].length();
int n = s.length(), m = words.length;
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < subLen; ++i) {
Map<String, Integer> cnt1 = new HashMap<>();
int l = i, r = i;
int t = 0;
while (r + subLen <= n) {
String w = s.substring(r, r + subLen);
r += subLen;
if (!cnt.containsKey(w)) {
l = r;
cnt1.clear();
t = 0;
continue;
}
cnt1.put(w, cnt1.getOrDefault(w, 0) + 1);
++t;
while (cnt1.get(w) > cnt.get(w)) {
String remove = s.substring(l, l + subLen);
l += subLen;
cnt1.put(remove, cnt1.get(remove) - 1);
--t;
}
if (m == t) {
ans.add(l);
}
}
}
return ans;
}
}class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
unordered_map<string, int> cnt;
for (auto& w : words) cnt[w]++;
int subLen = words[0].size();
int n = s.size(), m = words.size();
vector<int> ans;
for (int i = 0; i < subLen; ++i) {
unordered_map<string, int> cnt1;
int l = i, r = i;
int t = 0;
while (r + subLen <= n) {
string w = s.substr(r, subLen);
r += subLen;
if (!cnt.count(w)) {
l = r;
t = 0;
cnt1.clear();
continue;
}
cnt1[w]++;
t++;
while (cnt1[w] > cnt[w]) {
string remove = s.substr(l, subLen);
l += subLen;
cnt1[remove]--;
--t;
}
if (t == m) ans.push_back(l);
}
}
return ans;
}
};class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
unordered_map<string, int> d;
for (auto& w : words) ++d[w];
vector<int> ans;
int n = s.size(), m = words.size(), k = words[0].size();
for (int i = 0; i < k; ++i) {
int cnt = 0;
unordered_map<string, int> t;
for (int j = i; j <= n; j += k) {
if (j - i >= m * k) {
auto s1 = s.substr(j - m * k, k);
--t[s1];
cnt -= d[s1] > t[s1];
}
auto s2 = s.substr(j, k);
++t[s2];
cnt += d[s2] >= t[s2];
if (cnt == m) ans.emplace_back(j - (m - 1) * k);
}
}
return ans;
}
};func findSubstring(s string, words []string) []int {
cnt := map[string]int{}
for _, w := range words {
cnt[w]++
}
subLen := len(words[0])
n, m := len(s), len(words)
var ans []int
for i := 0; i < subLen; i++ {
cnt1 := map[string]int{}
l, r := i, i
t := 0
for r+subLen <= n {
w := s[r : r+subLen]
r += subLen
if _, ok := cnt[w]; !ok {
l = r
t = 0
cnt1 = map[string]int{}
continue
}
cnt1[w]++
t++
for cnt1[w] > cnt[w] {
remove := s[l : l+subLen]
l += subLen
cnt1[remove]--
t--
}
if t == m {
ans = append(ans, l)
}
}
}
return ans
}public class Solution {
public IList<int> FindSubstring(string s, string[] words) {
var wordsDict = new Dictionary<string, int>();
foreach (var word in words)
{
if (!wordsDict.ContainsKey(word))
{
wordsDict.Add(word, 1);
}
else
{
++wordsDict[word];
}
}
var wordOfS = new string[s.Length];
var wordLength = words[0].Length;
var wordCount = words.Length;
for (var i = 0; i <= s.Length - wordLength; ++i)
{
var substring = s.Substring(i, wordLength);
if (wordsDict.ContainsKey(substring))
{
wordOfS[i] = substring;
}
}
var result = new List<int>();
for (var i = 0; i <= s.Length - wordLength * wordCount; ++i)
{
var tempDict = new Dictionary<string, int>(wordsDict);
var tempCount = 0;
for (var j = i; j <= i + wordLength * (wordCount - 1); j += wordLength)
{
if (wordOfS[j] != null && tempDict[wordOfS[j]] > 0)
{
--tempDict[wordOfS[j]];
++tempCount;
}
else
{
break;
}
}
if (tempCount == wordCount)
{
result.Add(i);
}
}
return result;
}
}