题目描述

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.

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

The matching should cover the entire input string (not partial).

Note:

• s could be empty and contains only lowercase letters a-z.
• p could be empty and contains only lowercase letters a-z, and characters like . or *.

题意：给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明:s 可能为空，且只包含从 a-z 的小写字母。p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

算法1

(动态规划) $O(n*m)$

题解：双字符串的匹配问题，可以用动态规划来做。

状态表示：dp[i][j]代表s的前i个字符和p的前j个字符是否匹配。

状态初始化：dp[0][0] = true，对于1 <= i <= m如果p[i - 1] = '*' && dp[0][i - 2]那么dp[0][i] = true，这对应着p以a*b*c*…开头的字符串，因为*可以代表0个字符，所以可以往后匹配。

状态转移：

• s[i - 1] == p[j - 1] || p[j - 1] == '.'，这时候是精准匹配，所以取决于s的前i - 1个字符和p的前j - 1个字符是否匹配。dp[i][j] = dp[i - 1][j - 1];

• p[j - 1] = '*'，这个时候就比较麻烦了，我们根据*前的字符和s当前字符能否匹配分为两种情况：

• 如果不能匹配，那么*只能代表0个字符，这时候取决于s的前i个字符和p的前j - 2个字符是否匹配。dp[i][j] = dp[i][j - 2];

• 如果能匹配有3种可能的情况，需要对这三种情况取或：

  1. *代表0个字符，这时候这时候取决于s的前i个字符和p的前j - 2个字符是否匹配。dp[i][j] = dp[i][j - 2];

  2. *代表1个字符，这时候这时候取决于s的前i个字符和p的前j - 1个字符是否匹配。dp[i][j] = dp[i][j - 1];(这里因为s的第i个字符已经和p的第j - 1个字符匹配了，所以也可以是dp[i][j] = dp[i - 1][j - 2])

  3. *代表多个字符，这时候取决于取决于s的前i - 1个字符和p的前j个字符是否匹配。dp[i][j] = dp[i - 1][j];这是因为如果*代表多个字符的时候，去掉s的第i个字符对匹配结果不影响。

C++ 代码

    bool isMatch(string s, string p) {
        int n = s.length(),m = p.length();
        vector<vector<bool>> dp(n + 1,vector<bool>(m + 1,false));
        dp[0][0] = true;
        for(int i = 1;i <= m ; i ++)
            if(p[i - 1] == '*' && dp[0][i - 2])
                dp[0][i] = true;
        for(int i = 1 ; i <= n; i ++)
        {
            for(int j = 1; j <= m ; j ++)
            {
                if(s[i - 1] == p[j - 1] || p[j - 1] == '.')
                    dp[i][j] = dp[i - 1][j - 1];
                else if(p[j - 1] == '*')
                {
                    if(s[i - 1] != p[j - 2] && p[j - 2] != '.')
                        dp[i][j] = dp[i][j - 2];
                    else
                        dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j];
                }
            }
        }
        return dp[n][m];
    }