資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究查詢給定 N 個單詞之後字串中出現的所有單詞
在這個問題中，我們將找到字串中每個出現在“words”陣列所有單詞之後的單詞。
解決這個問題的第一種方法是將字串分割成單詞，並將words[]陣列的元素與字串單詞進行匹配。如果我們在字串中按相同的順序找到words[]陣列的元素，則列印字串的下一個單詞。
另一種方法是建立一個包含words[]陣列所有元素的字串。之後，我們可以在alpha字串中找到該字串作為子字串。如果我們將其作為子字串找到，我們可以提取並列印下一個單詞。
問題陳述− 我們給定了一個長度為N的alpha字串。我們還給定了一個包含M個單詞的words[]陣列。我們需要列印給定字串中的每個單詞，這些單詞在“words[]”陣列中所有單詞按相同順序出現之後。
示例
輸入
alpha = "Javascript is good programming language and C++ is good programming abcd"; words = {"is", "good", "programming"};
輸出
language abcd
解釋 – 字串中的“language”和“abcd”單詞出現在“is good programming”之後。
輸入
alpha = "I'm a good programmer, and I'm a good person"; words = {"I'm", "a", "good"};
輸出
programmer person
解釋 – “programmer”和“person”出現在“I’m a good”子字串之後。
輸入
alpha = "Hello Users! How are you?"; words = {"Users", "are", "How"};
輸出
“”
解釋− alpha字串中不存在words[]元素的出現。因此，它列印空字串。
方法 1
在這種方法中，我們將給定字串的所有單詞都放入列表中。之後，我們將遍歷列表，從每個索引開始，我們將下一個M個單詞與words[]陣列的元素進行匹配，如果所有元素都匹配，我們將列印第M+1個單詞。
演算法
步驟 1 − 初始化str_words列表和temp_str字串。
步驟 2 − 在遍歷字串時，如果當前字元是空格，則將temp_Str推入str_words列表，並重新初始化temp_str字串。
步驟 3 − 否則，將當前字元追加到temp_str字串。
步驟 4 − 還要將最後一個單詞追加到str_words列表。
步驟 5− 現在，遍歷str_words列表。使用巢狀while迴圈來匹配從第p個索引開始的words陣列和str_words陣列的下一個M個元素。如果任何元素不匹配，則中斷迴圈。
步驟 6 − 如果巢狀迴圈的索引等於M，並且P + M小於str_words列表的大小，則從p + 1索引獲取單詞，並將其推入“res”列表。
步驟 7 − 返回“res”列表。
示例
#include <bits/stdc++.h>
using namespace std;
vector<string> findWords(string alpha, vector<string> &words) {
// To store string words
vector<string> str_words;
string temp_str = "";
// Get each word of the string
for (int p = 0; p < alpha.size(); ++p) {
if (alpha[p] == ' ') {
str_words.push_back(temp_str);
temp_str = "";
} else {
temp_str += alpha[p];
}
}
// Handling the last word
if (temp_str != "")
str_words.push_back(temp_str);
vector<string> res;
int words_len = words.size();
// Traverse the string words and match the given words
for (int p = 0; p <= str_words.size() - words_len; p++) {
int q = 0;
while (q < words_len) {
// If the word is not matched, break the loop
if (str_words[p + q] != words[q])
break;
q++;
}
// If all words are found, push the next word in the result
if (q == words_len && p + q < str_words.size())
res.push_back(str_words[p + q]);
}
return res;
}
int main() {
string alpha = "Javascript is good programming language and C++ is good programming abcd";
vector<string> words = {"is", "good", "programming"};
vector<string> res = findWords(alpha, words);
cout << "The words according to the problem statement are: ";
for (auto word : res)
cout << word << " ";
return 0;
}
輸出
The words according to the problem statement are: language abcd
時間複雜度− O(N*M) 用於遍歷字串和單詞列表。
空間複雜度− O(N) 用於將字串單詞儲存在列表中。
方法 2
在這種方法中，我們將透過空格分隔將words[]陣列的所有元素都追加起來。之後，我們將找到結果字串作為原始字串中的子字串。對於結果字串作為子字串的每次出現，我們都將在原始字串中找到下一個單詞。
演算法
步驟 1 − 初始化字串的“res”列表和“temp_str”字串。
步驟 2 − 透過空格分隔連線words[]陣列的所有單詞，並將它們儲存到“temp_str”字串中。
步驟 3 − 開始遍歷原始字串。
步驟 4 − 如果從原始字串中的當前索引開始的子字串與temp_str字串相同，請執行以下步驟。
步驟 5 − 使用p + temp_str字串的長度初始化“q”。之後，使用迴圈並遞增“q”，直到我們到達末尾或下一個空格字元。
步驟 6 − 接下來，獲取從“p + temp_len”索引開始且長度為“q − p − temp_len”的子字串，並將其推入“res”列表。
步驟 7 − 返回“res”列表。
示例
#include <bits/stdc++.h>
using namespace std;
vector<string> findWords(string alpha, vector<string> &words) {
vector<string> res;
string temp_str = "";
// Merge all words in a single string
for (int p = 0; p < words.size(); p++) {
temp_str += words[p];
temp_str += " ";
}
int temp_len = temp_str.size();
// Traverse the alpha string and match given words
for (int p = 0; p <= alpha.size() - temp_len; p++) {
// Check if temp_str exists as a substring starting from p index
if (alpha.substr(p, temp_len) == temp_str) {
// Get next word
int q = p + temp_len;
while (q < alpha.size() && alpha[q] != ' ')
q++;
string next_word = alpha.substr(p + temp_len, q - p - temp_len);
res.push_back(next_word);
}
}
return res;
}
int main() {
string alpha = "Javascript is good programming language and C++ is good programming abcd";
vector<string> words = {"is", "good", "programming"};
vector<string> res = findWords(alpha, words);
cout << "The words according to the problem statement are: ";
for (auto word : res)
cout << word << " ";
return 0;
}
輸出
The words according to the problem statement are: language abcd
時間複雜度− O(N*M)，其中O(N)用於遍歷原始字串，O(M)用於查詢子字串
空間複雜度− O(M) 用於儲存臨時字串。
我們學習了兩種解決問題的方法。第一種比較單詞列表，另一種將由words[]列表的元素組成的結果字串與原始字串的子字串進行比較。兩種方法具有相同的時間和空間複雜度，因此程式設計師可以使用任何一種方法來獲得更好的效能。
91 次瀏覽
