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

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

注意：

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

Example 1:
Input:
Pattern: a.b
    Valid Strings:
        acb - any character can be present in place of "."
        aab - same reason as above
        adb - same reason as above

    In-Valid Strings:
        ab - Because in middle some element should be there to fill the place of "."
        acab - "." can hold 上 ly 1 element
        cb - because "a" is not presenet.

Example 2:
Pattern: a*b
    Valid Strings:
        b - because * matches 0 or more character of the element behind it
        ab - same reson as above
        aab 
        aaab
    In-Valid Strings:
        a - because "b" should be present at the end.
        acb - because * accepts elements of preceding element. As * is preceding by "a". This pattern is invalid.

Example 3: 
Pattern: a * b . * y
   Here 
    a* will accept 0 or more occurance of a
    b 上 e "b" should be present
    . * 0 or more occurance of any character
    y 上 e "y" at the end should be prensent.
 
Valid Strings:
    by
    bly
    ably

In-Valid Strings:
    ay
    ab

我们通过使用 自下而上 动态编程方法。

首先，我们采用布尔2D矩阵“bArray[i] [j] ”存储真值。然后，我们遍历所有元素并填充布尔数组。

哪里“i”代表字符串的索引“s”.
和“j”代表图案索引“p”

For any value of bArray [i] [j]will be equal to 上 e of the below 4 conditions:

Condition 1:
The value of bArray [i] [j]will be equall to the value of bArray[i -1 ] [j -1] when string [i] == pattern [j] || pattern [j] == '.'

Condition 2:
The value of bArray [i] [j]will be equall to the value of bArray[i] [j -2] if the pattern [j] == "*".

Condition 3:
The value of bArray [i] [j]will be equall to the value of bArray[i - 1] [j] when string [i] == pattern [j - 1] || pattern [j - 1] == '.'

Condition 4:
The value of bArray [i] [j]will be false, when string [i] is not equal to pattern [j].

我们来看一个例子：

Pattern = x a * b . c
String = x a a b y c

上面的字符串可以如下显示：

bArray [0] [0]为真。因为我们考虑过字符串为空，而模式也为空。因此，这是真的。第0列为假。因为我们已经考虑过字符串为空，但是模式不是。因此，我们将其写为假。

第0行也为假。因为我们的模式没有’不允许使用空字符串。如果我们的模式是类型” a * b *”那么它将接受空字符串。

在这里，0 =零

Lets start by taking the elements from bArray[1] [1], string[1] = x 和pattern [1] = x. Then we have to apply condition 1. hence the value of bArray[1] [1] will be bArray[i-1] [j-1] i.e bArray[0] [0] that is true.
Hence bArray[1] [1] = true.

bArray[1] [2], string[1] = x, pattern[2] = a. Condition 4 is applied. Hence the value of bArray[1] [2]  will be false.

bArray[1] [3], string [1] =x, pattern[3] = "*". In this case, we can have 0 or more occurance of a. Hence condition 2 is applied, i.e. bArray[i] [j- 2] the value is true.
	Here the pattern is "x a *" 和the string is "x", it can match 0 or more occurance of a. Hence it is true.
	Hence bArray[1] [3] = true.

bArray[1] [4], string[1] = x, pattern[4] = b contidtion 4, false.

bArray[1] [5], string[1] = x, pattern[5] = ".", Condition 1. The value of bArray[i - 1] [j - 1], bArray[0] [4] is false. Hence the result is false.

bArray[1] [6], string[1] = x, pattern[6] = c. Condition 4, false.

通道1之后的最终陈述如下：

所有遍历之后矩阵的最终表示：

最终的答案是“True”因此字符串与模式匹配。

时间复杂度为 O（米* n），因为对于m中的每个字符串= 1，2，。 。对于模式n中的每个元素= 1，2，， 。 。我们只调用一次函数。

空间复杂度也 O（米* n），因为我们将布尔项保存在temp 2d数组中。

C ++解决方案

#include<iostream>
#include<string>
using namespace std;

bool checkRegrex (string str, string pattern)
{
    bool bArray[str.length()] [pattern.length()];

    memset(bArray, false, sizeof(bool)*(str.length()+1)*(pattern.length()+1));

    bArray[0] [0] = true;

// to handle sitations like  a* or a*b* or a*b*c*
    for(int j = 1; j<=pattern.length() ; j++)
    {
        bArray[0][j] = pattern[j-1] == '*' ? bArray[0][j-2] : false;
    }

// we execute codition 1, 2, 3 和4 in this for loop
      for(int i = 1; i <= str.length(); i++)
    {
        for(int j = 1; j <= pattern.length(); j++)
        {

            if (pattern[j - 1] == '.' || pattern[j - 1] == str[i - 1]) 
            {
                    bArray[i][j] = bArray[i-1][j-1];
            } 
            else if (pattern[j - 1] == '*')  
            {
                    bArray[i][j] = bArray[i][j - 2];
                    if (pattern[j-2] == '.' || pattern[j - 2] == str[i - 1]) 
                    {
                        bArray[i][j] = bArray[i][j] | bArray[i - 1][j];
                    }
            } else {
                    bArray[i][j] = false;
                }

        }
    }


   return bArray[str.length()][pattern.length()];
}


int main()
{
      
    bool result = false;
       result = checkRegrex("abab", "a*");

       if(result)
       {
            cout<<"Pattern 和string is a match"<<endl;
       }
       else
       {
            cout<<"Pattern 和string is NOT a match"<<endl;
       }
}

输出：

Pattern 和string is a match

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