30. Substring with Concatenation of All Words
給定一個字符串 s 和一個字符串數組 words。words 中所有字符串的長度相同。
一個連接字符串是一個恰好包含任意排列的 words 中所有字符串的連接字符串。
例如，如果 words = ["ab","cd","ef"]，那麼 "abcdef", "abefcd", "cdabef", "cdefab", "efabcd" 和 "efcdab" 都是連接字符串。而 "acdbef" 不是連接字符串，因為它不是 words 任意排列的連接。
返回所有在 s 中連接子字符串的起始索引數組。你可以按任意順序返回答案。
範例 1：
輸入：s = "barfoothefoobarman", words = ["foo","bar"]
輸出：[0,9]
解釋：
從索引 0 開始的子字符串是 "barfoo"。它是 ["bar","foo"] 的連接，這是 words 的一個排列。 從索引 9 開始的子字符串是 "foobar"。它是 ["foo","bar"] 的連接，這是 words 的一個排列。
Python
from typing import List
from collections import Counter
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
if not s or not words or len(words) == 0 or len(words[0]) == 0:
return []
word_length = len(words[0])
num_words = len(words)
substring_length = word_length * num_words
word_count = Counter(words)
results = []
for i in range(word_length):
left = i
right = i
current_count = Counter()
while right + word_length <= len(s):
word = s[right:right + word_length]
right += word_length
if word in word_count:
current_count[word] += 1
while current_count[word] > word_count[word]:
current_count[s[left:left + word_length]] -= 1
left += word_length
if right - left == substring_length:
results.append(left)
else:
current_count.clear()
left = right
return results
17.39MB, 84ms
C++
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
using namespace std;
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> results;
if (s.empty() || words.empty() || words[0].empty()) {
return results;
}
int word_length = words[0].size();
int num_words = words.size();
int substring_length = word_length * num_words;
unordered_map<string, int> word_count;
for (const auto& word : words) {
++word_count[word];
}
for (int i = 0; i < word_length; ++i) {
int left = i, right = i;
unordered_map<string, int> current_count;
while (right + word_length <= s.size()) {
string word = s.substr(right, word_length);
right += word_length;
if (word_count.find(word) != word_count.end()) {
++current_count[word];
while (current_count[word] > word_count[word]) {
string left_word = s.substr(left, word_length);
--current_count[left_word];
left += word_length;
}
if (right - left == substring_length) {
results.push_back(left);
}
} else {
current_count.clear();
left = right;
}
}
}
return results;
}
};
22.81MB, 31ms
Javascript
/**
* @param {string} s
* @param {string[]} words
* @return {number[]}
*/
var findSubstring = function(s, words) {
const results = [];
if (s.length === 0 || words.length === 0 || words[0].length === 0) {
return results;
}
const wordLength = words[0].length;
const numWords = words.length;
const substringLength = wordLength * numWords;
const wordCount = new Map();
// Count the frequency of each word in words
for (const word of words) {
wordCount.set(word, (wordCount.get(word) || 0) + 1);
}
// Sliding window over every possible starting point within the word length range
for (let i = 0; i < wordLength; i++) {
let left = i, right = i;
const currentCount = new Map();
while (right + wordLength <= s.length) {
const word = s.substring(right, right + wordLength);
right += wordLength;
if (wordCount.has(word)) {
currentCount.set(word, (currentCount.get(word) || 0) + 1);
while (currentCount.get(word) > wordCount.get(word)) {
const leftWord = s.substring(left, left + wordLength);
currentCount.set(leftWord, currentCount.get(leftWord) - 1);
left += wordLength;
}
if (right - left === substringLength) {
results.push(left);
}
} else {
currentCount.clear();
left = right;
}
}
}
return results;
};
56.95MB, 70ms
