根据给定的模式检查给定句子中的单词是否出现
在这个问题中，我们需要检查字符串是否遵循给定的模式。我们可以通过将每个字符映射到单词来解决问题。如果模式中的任何字符映射多个单词，我们可以说字符串不遵循模式。
问题陈述 – 我们给出了一个包含 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"字符串不为空且不存在于映射中，则将"tempStr"和"charPointer"值加 1 后插入到映射中。
步骤 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) {
// 存储字符串的单词
map<string, int> words;
int charPointer = -1;
string tempStr = "";
string str = "";
// 开始遍历字符串
for (int a = 0; a < alpha.length(); a++) {
// 如果得到空格，则表示单词已完成
if (alpha[a] == ' ') {
// 如果映射中不存在某个单词，则添加它
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'));
}
// Re-initialization
tempStr = "";
} else {
// Get word
tempStr += alpha[a];
}
}
// 处理最后一个单词
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 = "";
// 为模式创建映射
for (int a = 0; a < pat.length(); a++) {
// 将字符插入到映射中
if (patternMap.find(pat[a]) == patternMap.end())
patternMap.insert({pat[a], ++charPointer});
// 如果字符已存在
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 << "字符串遵循给定的模式";
} else {
cout << "字符串不遵循给定的模式";
}
return 0;
}
输出
字符串遵循给定的模式
时间复杂度 – O(NlogN)，因为我们在地图中搜索。
空间复杂度 – O(N)，因为我们使用地图数据结构。
在解决方案中，我们创建并匹配了两个字符串的通用模式。然而，程序员可以在不创建通用模式的情况下解决问题，但需要交叉检查单个字符不应映射到不同的单词，单个单词不应映射到不同的字符。
