C ++中的通配符匹配

给定一个输入字符串（s）和一个模式（p），实现通配符模式匹配并支持‘?’ and ‘*’.

'?' Matches any single character.

'*' Matches any sequence of characters (including the empty sequence).

匹配应覆盖整个输入字符串。

Example 1:

Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:

Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

Example 5:

Input:
s = "acdcb"
p = "a*c?b"
Output: false

建议您先阅读类似的问题“正则表达式匹配”。

使用动态编程可以解决此问题。我们将采用一个布尔数组，并根据以下2个公式对其进行更新。在数组的末尾，我们将得到结果。

式：

1. boolean_array[i][j] = boolean_array[i-1][j-1] if the value at boolean_array[i][j] is a character or a “?”.

2. boolean_array[i][j] = boolean_array[i][j-1] || boolean_array[i-1][j] if the value at at boolean_array[i][j] is “*”.

为了更好地理解问题，我们将举一个例子并逐步解决。

在我们的示例中

String = “xaylmz”

Pattern = “x?y*z”

初始布尔数组如下所示：

boolean_array [0] [0] = True。 因为考虑一个空字符串和一个空模式，所以它们都将匹配。因此是真的。

boolean_array [0] [1] = False。 因为模式是“ x”，字符串是“ null”。他们将不匹配。因此是错误的。

通过相同的分析，整个列将变为假，如下所示。

现在， boolean_array [1] [0] = False。因为模式为“ null”，而字符串为“ x”。他们将不匹配。因此，整行将为假。

现在， boolean_array [1] [1] = True。因为模式是“ x”，字符串也是“ x”。这符合我们的第一个条件。布尔数组[1] [1]的值=布尔数组[0] [0]，为true。

现在， boolean_array [1] [2] = False。因为模式是“ x？”字符串是“ x”。这符合我们的第一个条件。布尔数组[1] [2] =布尔数组[0] [1]的值为False。

现在， boolean_array [1] [3] = False。因为模式是“ y”，字符串是“ x”。因此是错误的。

现在， boolean_array [1] [4] = False。由于模式为“ *”，因此我们查看左侧和顶部的值（以紫色表示），因为两者均为假，所以结果为假。

现在， boolean_array [1] [5] = False。由于模式为“ z”，字符串为“ x”，因此为false。

求解完所有索引后，最终将获得值“ true”，如下图的绿色所示。

C ++解决方案

#include<iostream>
#include<vector>

using namespace std;

bool isMatch(string str, string pattern) 
{
	bool bool_array [str.size()+1] [pattern.size()+1];

	//initialize boolean array to false.
	for (int i = 0; i <= str.size(); ++i)
	{
		for (int j = 0; j <= pattern.size(); ++j)
		{
			bool_array[i][j] = 0;
		}
	}

	// base case
	bool_array[0][0] = true;


	for (int i = 1; i <= str.size(); i++)
	{
		for (int j = 1; j <= pattern.size(); j++)
		{
			if (str[i-1] == pattern[j-1] || pattern[j-1] == '?')
				bool_array[i][j] = bool_array[i-1][j-1];

			else if (pattern[j-1] == '*')
				bool_array[i][j] = bool_array[i][j-1] || bool_array[i-1][j];
		}
	}

	return bool_array[str.size()][pattern.size()];
}

int main()
{
	string str = "xaylmz";
	string pattern = "x?y*z";

	bool result = isMatch(str, pattern);

	if(result)
		cout<<" The pattern and string matches"<<endl;
	else
		cout<<" The pattern and string does not match"<<endl;

	return 0;
}

输出：

 The pattern and string matches

该网站上可用的教程列表：