class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
}
};
30. 串联所有单词的子串
给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。
示例 1：
输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
示例 2：
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
示例 3：
输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] 输出：[6,9,12]
提示：
1 <= s.length <= 104s 由小写英文字母组成1 <= words.length <= 50001 <= words[i].length <= 30words[i] 由小写英文字母组成相似题目
原站题解
golang 解法, 执行用时: 17 ms, 内存消耗: 6.9 MB, 提交时间: 2024-04-23 14:40:49
func findSubstring(s string, words []string) (ans []int) {
ls, m, n := len(s), len(words), len(words[0])
for i := 0; i < n && i+m*n <= ls; i++ {
differ := map[string]int{}
for j := 0; j < m; j++ {
differ[s[i+j*n:i+(j+1)*n]]++
}
for _, word := range words {
differ[word]--
if differ[word] == 0 {
delete(differ, word)
}
}
for start := i; start < ls-m*n+1; start += n {
if start != i {
word := s[start+(m-1)*n : start+m*n]
differ[word]++
if differ[word] == 0 {
delete(differ, word)
}
word = s[start-n : start]
differ[word]--
if differ[word] == 0 {
delete(differ, word)
}
}
if len(differ) == 0 {
ans = append(ans, start)
}
}
}
return
}
javascript 解法, 执行用时: 95 ms, 内存消耗: 56.3 MB, 提交时间: 2024-04-23 14:40:35
/**
* @param {string} s
* @param {string[]} words
* @return {number[]}
*/
var findSubstring = function(s, words) {
const res = [];
const m = words.length, n = words[0].length, ls = s.length;
for (let i = 0; i < n; i++) {
if (i + m * n > ls) {
break;
}
const differ = new Map();
for (let j = 0; j < m; j++) {
const word = s.substring(i + j * n, i + (j + 1) * n);
differ.set(word, (differ.get(word) || 0) + 1);
}
for (const word of words) {
differ.set(word, (differ.get(word) || 0) - 1);
if (differ.get(word) === 0) {
differ.delete(word);
}
}
for (let start = i; start < ls - m * n + 1; start += n) {
if (start !== i) {
let word = s.substring(start + (m - 1) * n, start + m * n);
differ.set(word, (differ.get(word) || 0) + 1);
if (differ.get(word) === 0) {
differ.delete(word);
}
word = s.substring(start - n, start);
differ.set(word, (differ.get(word) || 0) - 1);
if (differ.get(word) === 0) {
differ.delete(word);
}
}
if (differ.size === 0) {
res.push(start);
}
}
}
return res;
};
cpp 解法, 执行用时: 74 ms, 内存消耗: 38.7 MB, 提交时间: 2024-04-23 14:40:20
class Solution {
public:
vector<int> findSubstring(string &s, vector<string> &words) {
vector<int> res;
int m = words.size(), n = words[0].size(), ls = s.size();
for (int i = 0; i < n && i + m * n <= ls; ++i) {
unordered_map<string, int> differ;
for (int j = 0; j < m; ++j) {
++differ[s.substr(i + j * n, n)];
}
for (string &word: words) {
if (--differ[word] == 0) {
differ.erase(word);
}
}
for (int start = i; start < ls - m * n + 1; start += n) {
if (start != i) {
string word = s.substr(start + (m - 1) * n, n);
if (++differ[word] == 0) {
differ.erase(word);
}
word = s.substr(start - n, n);
if (--differ[word] == 0) {
differ.erase(word);
}
}
if (differ.empty()) {
res.emplace_back(start);
}
}
}
return res;
}
};
java 解法, 执行用时: 19 ms, 内存消耗: 44.7 MB, 提交时间: 2024-04-23 14:40:06
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<Integer>();
int m = words.length, n = words[0].length(), ls = s.length();
for (int i = 0; i < n; i++) {
if (i + m * n > ls) {
break;
}
Map<String, Integer> differ = new HashMap<String, Integer>();
for (int j = 0; j < m; j++) {
String word = s.substring(i + j * n, i + (j + 1) * n);
differ.put(word, differ.getOrDefault(word, 0) + 1);
}
for (String word : words) {
differ.put(word, differ.getOrDefault(word, 0) - 1);
if (differ.get(word) == 0) {
differ.remove(word);
}
}
for (int start = i; start < ls - m * n + 1; start += n) {
if (start != i) {
String word = s.substring(start + (m - 1) * n, start + m * n);
differ.put(word, differ.getOrDefault(word, 0) + 1);
if (differ.get(word) == 0) {
differ.remove(word);
}
word = s.substring(start - n, start);
differ.put(word, differ.getOrDefault(word, 0) - 1);
if (differ.get(word) == 0) {
differ.remove(word);
}
}
if (differ.isEmpty()) {
res.add(start);
}
}
}
return res;
}
}
python3 解法, 执行用时: 120 ms, 内存消耗: 15.5 MB, 提交时间: 2022-07-28 15:29:32
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
res = []
m, n, ls = len(words), len(words[0]), len(s)
for i in range(n):
if i + m * n > ls:
break
differ = Counter()
for j in range(m):
word = s[i + j * n: i + (j + 1) * n]
differ[word] += 1
for word in words:
differ[word] -= 1
if differ[word] == 0:
del differ[word]
for start in range(i, ls - m * n + 1, n):
if start != i:
word = s[start + (m - 1) * n: start + m * n]
differ[word] += 1
if differ[word] == 0:
del differ[word]
word = s[start - n: start]
differ[word] -= 1
if differ[word] == 0:
del differ[word]
if len(differ) == 0:
res.append(start)
return res