資料結構
網路
關係資料庫管理系統(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 次瀏覽
