C++ 根据给定的模式检查句子中的单词是否出现

在这个问题中，我们需要检查字符串是否遵循给定的模式。我们可以通过将每个字符映射到单词来解决这个问题。如果模式的任何字符映射了多个单词，我们可以说该字符串不遵循该模式。

问题陈述 - 我们已经给定一个包含N个字符的’pat’字符串和一个包含N个单词的’alpha’字符串。给定的任务是检查’alpha’字符串是否遵循’pat’字符串的模式。

注意 - 当单词按顺序匹配’pat’的字符时，我们可以说’alpha’字符串遵循该模式。

示例示例

输入

pat = "ana", alpha = "Hello hi Hello";

输出

‘Yes’

解释 – 给定的字符串遵循该模式，因为 a -> ‘Hello’，b -> ‘hi’。

输入

pat = "aba"; alpha = "Welcome to Tutorialspoint!";

输出结果

‘No’

解释 - 让我们来看一下字符映射与字符串的词语。

a – > ‘欢迎’
b -> ‘到’
a -> ‘教程点’

在这里，’a’映射到多个词语，所以我们可以说字符串不遵循模式。

输入

pat = "bbb"; alpha = "orange orange orange";

输出

‘Yes’

说明 - 字符串遵循以下模式

方法 1

在这种方法中，我们需要找到“pat”字符串和“alpha”字符串所遵循的模式。然后，我们可以比较两个模式，确保“pat”字符串和“alpha”字符串的模式是否匹配。

算法

步骤 1 - 初始化“words”映射，将数字值映射到字符串单词，“charPointer”指向字符串字符，“tempStr”存储单词，“str”存储字符串中的单词模式。

步骤 2 - 开始遍历“alpha”字符串。

步骤 3 - 如果当前字符为空格，则执行以下步骤。否则，将一个字符添加到“tempStr”字符串中。

步骤 4 - 如果“tempStr”字符串非空且不存在于映射中，则在将其递增1后，将“tempStr”和“charPointer”值插入到映射中。

步骤 5 - 如果“tempStr”存在于映射中，则获取映射的数字值，并将相关字符值附加到“str”字符串中。

步骤 6 - 同样，使用空字符串重新初始化“tempStr”。

步骤 7 - 当迭代完成时，处理字符串的最后一个单词。

步骤 8 - 初始化“patternMap”映射，用于存储“pat”字符串字符的模式，以及“final_pat”字符串，用于存储模式。

步骤 9 - 遍历“pat”字符串。如果字符串字符不存在于映射中，则将字符与“charPointer”值插入映射中。

步骤 10 - 接下来，从映射中获取与字符相关联的映射值，并将其附加到“final_pat”字符串中。

步骤 11 - 最后，如果final_pat和str字符串匹配，则返回true。否则，返回false。

示例

#include <bits/stdc++.h>
using namespace std;

bool isPatternExists(string pat, string alpha) {
    // To store words of the string
    map<string, int> words;
    int charPointer = -1;
    string tempStr = "";
    string str = "";
    // Start traversing the string
    for (int a = 0; a < alpha.length(); a++) {
        // If we get the space, the word is completed
        if (alpha[a] == ' ') {
            // If a word does not exist in the map, add it
            if (!tempStr.empty() && words.find(tempStr) == words.end()) {
                words.insert({tempStr, ++charPointer});
            }
            if (words.find(tempStr) != words.end()) {
                // If word exists
                str += ((char)((words.find(tempStr))->second + 'a'));
            }
            // Re-initialization
            tempStr = "";
        } else {
            // Get word
            tempStr += alpha[a];
        }
    }
    // Handling the last word
    if (!tempStr.empty() && words.find(tempStr) == words.end())
        words.insert({tempStr, ++charPointer});
    if (words.find(tempStr) != words.end())
        str += ((char)((words.find(tempStr))->second + 'a'));
    map<char, int> patternMap;
    charPointer = -1;
    string final_pat = "";
    // Create the mapping for the pattern
    for (int a = 0; a < pat.length(); a++) {
        // Insert char to map
        if (patternMap.find(pat[a]) == patternMap.end())
            patternMap.insert({pat[a], ++charPointer});
        // If character already exists
        if (patternMap.find(pat[a]) != patternMap.end())
            final_pat += ((char)((patternMap.find(pat[a]))->second + 'a'));
    }
    return final_pat == str;
}
int main() {
    string pat = "ana";
    string alpha = "Hello hi Hello";
    if (isPatternExists(pat, alpha)) {
        cout << "The string follows the given pattern";
    } else {
        cout << "The string does not follow the given pattern";
    }
    return 0;
}