查找给定 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[]列表的元素组成的结果字符串与原始字符串的子字符串进行比较。两种方法具有相同的时间和空间复杂度,因此程序员可以使用任何一种方法来获得更好的性能。