检查给定的模式是否存在于给定的字符串中，包括通配符 * 和 .
检查给定的模式是否存在于给定的字符串中，包括通配符 * 和 . 是计算机科学和编程中常见的问题。在这个问题中，我们给出了一个字符串(文本)和一个模式，它可以包含通配符"*"和"。"，我们需要检查模式是否与文本匹配。这个问题在各种应用中都会遇到，例如搜索引擎、文件系统和网络协议。
在本教程中，我们将讨论使用 C++ 解决此问题的简单而有效的方法。我们将首先解释问题陈述及其约束，然后我们将提供解决该问题的分步指南。我们还将提供一个实现我们解决方案的示例 C++ 代码，并讨论其时间和空间复杂度。那么让我们开始吧!
问题陈述
目标是确定包含通配符"*"和"•"的给定模式是否与给定的文本字符串匹配。模式和文本的长度分别为 M 和 N。如果模式与文本匹配，则输出"是"。否则，输出"否"。
应该注意的是，"*"字符匹配零个或多个紧接在其前面的字符，而"•"字符匹配任何单个字符。
示例 1
输入
文本:"hello world"；模式:"h*llo w•rld"
输出
Yes
说明:在此示例中，文本为"hello world"，模式为"hllo w•rld"。模式中的 '' 字符匹配紧接在其之前的字符的零个或多个出现次数。因此，它与文本中的 'h' 匹配。'•' 字符匹配任何单个字符，因此它与文本中的空格字符匹配。该模式还匹配文本中的 'o' 和 'w' 字符。因此，模式与文本匹配，输出为"是"。
示例 2
输入
文本:"cat"；模式:"c*t•"
输出
No
解释:在此示例中，文本为"cat"，模式为"ct•"。模式中的 ' 字符匹配紧接在其之前的字符的零个或多个出现。因此，它与文本中的 'c' 匹配。'•' 字符匹配任何单个字符，因此它与文本中的 'a' 字符匹配。但是，模式与文本中的最后一个 't' 字符不匹配，因为没有 '•' 字符与之匹配。因此，模式与文本不匹配，输出为"否"。
算法
1.初始化一个矩阵 dp，其维度为 (n+1) x (m+1)，其中 dp[i][j] 表示文本中索引为 i 的子字符串是否与模式中索引为 j 的子字符串匹配。
2. 将 dp[0][0] 设置为 true，因为空文本和空模式始终匹配。
3. 迭代模式中从索引 1 到 m 的每个字符:
如果当前字符为 ''，则将 dp[0][i] 设置为 dp[0][i-1]，表示 '' 可以匹配空子字符串。
4.迭代文本中从索引 1 到 n 的每个字符:
对于模式中从索引 1 到 m 的每个字符:
如果文本和模式中当前位置的字符相同，或者模式字符为 '?'，则将 dp[i][j] 设置为 dp[i-1][j-1]，因为当前字符匹配。
如果模式字符为 ''，则将 dp[i][j] 设置为 dp[i][j-1](表示 '' 匹配空子字符串)或 dp[i-1][j](表示 '*' 匹配当前文本字符)。
否则，将 dp[i][j] 设置为 false。
5.最终结果存储在 dp[n][m] 中，表示整个文本是否与整个模式匹配。
该算法使用动态规划方法构建矩阵，考虑模式中每个字符的三种可能情况:匹配文本中的字符、匹配"?"或匹配"*"。如果整个文本与整个模式匹配，则算法返回 true，否则返回 false。
示例
使用 C++ 实现上述算法
以下 C++ 程序旨在确定给定文本是否与包含"*"和"?"符号表示的通配符的模式匹配。该算法利用动态规划构建矩阵 dp[n+1][m+1]，其中 n 是文本的长度，m 是模式的长度。
输入
"hello world"; string pattern = "h*llo w?rld";
输出
Yes
示例
#include <iostream>
#include <vector>
bool isMatch(const std::string& text, const std::string& pattern) {
int n = text.length();
int m = pattern.length();
std::vector<std::vector<bool>> dp(n + 1, std::vector<bool>(m + 1, false));
dp[0][0] = true;
for (int i = 1; i <= m; i++) {
if (pattern[i - 1] == '*') {
dp[0][i] = dp[0][i - 1];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (text[i - 1] == pattern[j - 1] || pattern[j - 1] == '?') {
dp[i][j] = dp[i - 1][j - 1];
} else if (pattern[j - 1] == '*') {
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
} else {
dp[i][j] = false;
}
}
}
return dp[n][m];
}
int main() {
std::string text = "hello world";
std::string pattern = "h*llo w?rld";
if (isMatch(text, pattern)) {
std::cout << "Yes\n";
} else {
std::cout << "No\n";
}
return 0;
}
输出
Yes
结论
总之，所提供的程序使用动态规划实现了模式匹配算法。它确定给定的文本是否与包含通配符"*"和"?"符号的模式匹配。通过构建矩阵并迭代比较字符，该算法可以有效地评估匹配条件。独特的方法可确保准确的模式匹配结果，从而实现多种文本比较。该程序是各种应用的宝贵工具，例如字符串匹配、文本处理和数据分析。它的效率和可靠性使其成为处理模式匹配任务时的可靠选择。
