检查给定字符串中是否存在给定模式，包括通配符 * 和 .。

---

检查给定字符串中是否存在给定模式（包括通配符 * 和 .）是计算机科学和编程中的一个常见问题。在这个问题中，我们得到一个字符串（文本）和一个模式，它可能包含通配符字符 '*' 和 '.'，我们需要检查模式是否与文本匹配。这个问题在许多应用中都会遇到，例如搜索引擎、文件系统和网络协议。

在本教程中，我们将讨论使用C++解决此问题的一个简单有效的解决方案。我们将首先解释问题陈述及其约束条件，然后逐步指导您解决问题。我们还将提供一个实现我们解决方案的C++代码示例，并讨论其时间和空间复杂度。让我们开始吧！

问题陈述

目标是确定给定的包含通配符字符 '*' 和 '•' 的模式是否与给定的文本字符串匹配。模式和文本的长度分别为M和N。如果模式与文本匹配，则输出“Yes”。否则，输出“No”。

需要注意的是，'*' 字符匹配其前面字符的零个或多个出现，而 '•' 字符匹配任何单个字符。

示例1

输入

Text: "hello world"; Pattern: "h*llo w•rld"

输出

Yes

解释：在这个例子中，文本是“hello world”，模式是“hllo w•rld”。模式中的''字符匹配其前面字符的零个或多个出现。因此，它匹配文本中的'h'。'•'字符匹配任何单个字符，因此它匹配文本中的空格字符。模式也匹配文本中的'o'和'w'字符。因此，模式与文本匹配，输出为“Yes”。

示例2

输入

Text: "cat"; Pattern: "c*t•"

输出

No

解释：在这个例子中，文本是“cat”，模式是“ct•”。模式中的''字符匹配其前面字符的零个或多个出现。因此，它匹配文本中的'c'。'•'字符匹配任何单个字符，因此它匹配文本中的'a'字符。但是，模式与文本中的最终't'字符不匹配，因为没有'•'字符与之匹配。因此，模式与文本不匹配，输出为“No”。

算法

1. 初始化一个维度为(n+1) x (m+1)的矩阵dp，其中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

结论

总而言之，提供的程序使用动态规划实现了模式匹配算法。它确定给定的文本是否与包含通配符'*'和'?'符号的模式匹配。通过构建矩阵并迭代地比较字符，该算法有效地评估匹配条件。这种独特的方法确保了精确的模式匹配结果，允许进行多功能的文本比较。该程序可作为各种应用程序的有价值工具，例如字符串匹配、文本处理和数据分析。其效率和可靠性使其成为处理模式匹配任务时的可靠选择。