数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中所有单词的串联子字符串
假设我们有一个字符串 s，我们还有一个单词列表 words，数组中存在的单词都具有相同的长度。我们必须找到 s 中所有子字符串的起始索引，这些子字符串是 words 中每个单词的精确串联，并且没有任何中间字符。
因此，如果输入类似于“barfoothefoobarman”并且单词为 [“foo”, “bar”]，则输出将为 [0,9]。这是因为从索引 0 和 9 开始的子字符串分别是“barfoo”和“foobar”。
为了解决这个问题，我们将遵循以下步骤：
定义一个名为 ok() 的方法，它将接收字符串 s、映射 wordCnt 和 n：
将 s 的副本复制到 temp 中
对于 i 从 n 到 s 的大小 - 1
如果 temp 的大小是 0 的倍数，则
如果 temp 不存在于 wordCnt 中，则返回 false
否则
如果 wordCnt[temp] 为 1，则从 wordCnt 中删除 temp，将 temp 设置为空字符串
否则将 wordCnt[temp] 的值减少 1，将 temp 设置为空字符串。
将 temp 增加 s[i]
如果 temp 不在 wordCnt 中，则返回 false
否则
如果 wordCnt[temp] 为 1，则从 wordCnt 中删除 temp，将 temp 设置为空字符串
否则将 wordCnt[temp] 的值减少 1，将 temp 设置为空字符串。
当 wordCnt 的大小为 0 时返回 true
从主方法中执行以下操作
如果 a 的大小为 0 或 b 的大小为 0，则返回空数组
创建一个映射 wordCnt，将 b 中存在的字符串的频率存储到 wordCnt 中
创建一个名为 ans 的数组
window := 单词数 x 每个单词中的字符数
将字符串 a 的一个副本复制到 temp 中
对于 i 从 window 到 a 的大小 - 1
如果 temp 大小可被 window 整除，并且调用 ok(temp, wordCnt, b[0] 的大小)，则
将 i - window 插入 ans 中
将 a[i] 插入 temp 中
如果 temp 的大小 > window，则删除从 0 到 1 的子字符串
如果 temp 大小可被 window 整除，并且调用 ok(temp, wordCnt, b[0] 的大小)，则
将 a 的大小 - window 插入 ans 中
返回 ans
示例
让我们看看以下实现以获得更好的理解：
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
bool ok(string s, unordered_map <string, int> wordCnt, int n){
string temp = "";
for(int i = 0; i < n; i++){
temp += s[i];
}
for(int i = n; i < s.size(); i++){
if(temp.size() % n == 0){
if(wordCnt.find(temp) == wordCnt.end())return false;
else{
if(wordCnt[temp] == 1){
wordCnt.erase(temp);
temp = "";
}
else{
wordCnt[temp]--;
temp = "";
}
}
}
temp += s[i];
}
if(wordCnt.find(temp) == wordCnt.end())return false;
else{
if(wordCnt[temp] == 1){
wordCnt.erase(temp);
temp = "";
}
else{
wordCnt[temp]--;
temp = "";
}
}
return wordCnt.size() == 0;
}
vector<int> findSubstring(string a, vector<string> &b) {
if(a.size() == 0 || b.size() == 0)return {};
unordered_map <string, int> wordCnt;
for(int i = 0; i < b.size(); i++)wordCnt[b[i]]++;
vector <int> ans;
int window = b.size() * b[0].size();
string temp ="";
for(int i = 0; i < window; i++)temp += a[i];
for(int i = window; i < a.size(); i++){
if(temp.size() % window == 0 && ok(temp, wordCnt, b[0].size())){
ans.push_back(i - window);
}
temp += a[i];
if(temp.size() > window)temp.erase(0, 1);
}
if(temp .size() % window ==0 && ok(temp, wordCnt, b[0].size()))ans.push_back(a.size() - window);
return ans;
}
};
main(){
vector<string> v = {"foo", "bar"};
Solution ob;
print_vector(ob.findSubstring("barfoothefoobarman", v));
}输入
1,2,3,4,5,6,7 3
输出
[0, 9, ]
126 次查看
