检查给定句子中出现的单词是否基于给定的模式

---

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

问题陈述 – 我们给定一个包含 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 -> ‘Welcome’

• b -> ‘to’

• a -> ‘Tutorialspoint’

这里，'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;
}

输出

The string follows the given pattern

时间复杂度 – O(NlogN)，因为我们在映射中搜索。

空间复杂度 – O(N)，因为我们使用映射数据结构。

在解决方案中，我们创建并匹配了两个字符串的通用模式。但是，程序员可以不创建通用模式来解决问题，但需要交叉检查单个字符不应映射到不同的单词，单个单词不应映射到不同的字符。