数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学查找由C++中列表(L)中所有单词连接而成的字符串(S)中子字符串的起始索引
假设我们有一个字符串s，还有一个包含一些单词的列表，这些单词长度相同。我们必须找到字符串s中所有子字符串的起始索引，这些子字符串是由列表b中的每个单词恰好连接一次构成的，并且没有任何其他字符。
例如，如果输入是“wordgoodgoodgoodword”并且单词列表是["word","good"]，则输出将是[0,12]。这是因为从索引0和12开始的子字符串分别是“wordgood”和“goodword”。
为了解决这个问题，我们将遵循以下步骤：
定义一个名为ok()的方法，它将接收字符串s，map wordCnt和n作为参数：
将s复制到temp中
对于i从n到s的长度-1
如果temp的长度是n的倍数，则
如果wordCnt中不存在temp，则返回false
否则
如果wordCnt[temp]为1，则从wordCnt中删除temp，并将temp设置为空字符串
否则，将wordCnt[temp]的值减少1，并将temp设置为空字符串。
将s[i]添加到temp中
如果wordCnt中不存在temp，则返回false
否则
如果wordCnt[temp]为1，则从wordCnt中删除temp，并将temp设置为空字符串
否则，将wordCnt[temp]的值减少1，并将temp设置为空字符串。
如果wordCnt的长度为0，则返回true
在主方法中，执行以下操作：
如果a的长度为0或b的长度为0，则返回空数组
创建一个map 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
示例(C++)
让我们来看下面的实现，以便更好地理解：
#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 = {"word","good"};
Solution ob;
print_vector(ob.findSubstring("wordgoodgoodgoodword", v));
}输入
“wordgoodgoodgoodword”, {"word","good"}输出
[0, 12, ]
144 次浏览
