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

更新于: 2023年7月17日

91 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始
广告