假设我们有一个字符串s,并且还有一个单词列表,数组中存在的单词长度都相同。我们必须找到s中所有子字符串的起始索引,该索引是每个单词在单词中的连接,且一次没有任何中间字符。
因此,如果输入像“ barfoothefoobarman”,而单词是[“ foo”,“ bar”],那么输出将是[0,9]。这是因为从索引0和9开始的子字符串是“ barfoo”和“ foobar”。
为了解决这个问题,我们将遵循以下步骤-
定义一个名为的方法ok()
,它将采用字符串s,映射wordCnt和n-
将s复制到临时文件
对于范围在n到s的i – 1
如果在wordCnt中不存在temp时,则返回false
除此以外
如果wordCnt [temp]为1,则从wordCnt删除temp,将temp设置为空字符串
否则,将wordCnt [temp]的值减小1,将temp设置为空字符串。
如果temp的大小是0的倍数,则
将温度提高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的数组
窗口:=单词数x每个单词中的字符数
将字符串a的一个副本复制到temp
对于范围窗口中的我,其大小为– 1
将i –窗口插入ans
如果临时大小可以被窗口整除并调用ok(temp,wordCnt,b [0]的大小),则
在温度中插入a [i]
如果temp的大小> window,则从0,1删除子字符串
如果临时大小可以被窗口整除并调用ok(temp,wordCnt,b [0]的大小),则
在窗口中插入一个–窗口的大小
返回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, ]