資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
