题目链接：Regular Expression Matching

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). 

The function prototype should be: 
bool isMatch(const char *s, const char *p) 

Some examples: 

isMatch("aa","a") → false 
isMatch("aa","aa") → true 
isMatch("aaa","aa") → false 
isMatch("aa", "a*") → true 
isMatch("aa", ".*") → true 
isMatch("ab", ".*") → true 
isMatch("aab", "c*a*b") → true

这道题的要求是判断字符串s能否和正则表达式p相匹配。其中’.’匹配任意单个字符，’*‘匹配0个或多个’*‘的前一字符。如果匹配能整个串返回true。

  1. 回溯暴力匹配

思路是进行递归回溯匹配。当p的下一个字符是’*‘的时候，则循环检测p与s的当前字符是否匹配（每次s后移1位，直到结束或者不匹配）；当p的下一个字符不是’*‘的时候，直接检测字符串是否结束或者p与s的当前字符是否匹配。注意’.’可以与任意单个字符匹配。

时间复杂度：???

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution
{
public:
    bool isMatch(const char *s, const char *p)
    {
        if(*p == '\0' )
            return *s == '\0';
        
        if(*(p + 1) == '*')
        {
            while(*s != '\0' && (*p == '.' || *s == *p))
            {
                if(isMatch(s, p + 2))
                    return true;
                ++ s;
            }
            return isMatch(s, p + 2);
        }
        else if(*s != '\0' && (*p == '.' || *s == *p))
            return isMatch(s + 1, p + 1);
        
        return false;
    }
};

  1. 动态规划

思路是使用bool类型的二维数组dp[m+1][n+1]（m、n分别为字符串s和p的长度）记录s和p是否匹配，即dp[i+1][j+1]表示s的前i个字符是否与p的前j的字符相匹配。

如果p[j]不等于’*‘，则dp[i + 1][j + 1] = dp[i][j] && s[i] == p[j]

如果p[j]等于’*‘，则当且仅当在下面三种情况为真，dp[i + 1][j + 1]为真：

  • ’*‘前面字符重复出现0次，则p字符串需要往前看2位，即dp[i + 1][j - 1]是否为真

  • ’*‘前面的字符重复出现1次，则p字符串只需要往前看1位，即dp[i + 1][j]是否为真

  • ’*‘前面的字符重复出现次数大于1次，则s字符串需要往前看1位，即dp[i][j + 1]是否为真，以及s字符串当前字符（s[i]）与p字符串’*‘前面字符（p[j - 1]）是否相匹配。

注意，’.’可以与任意单个字符匹配。

注：动态规划思路是参考的这里。这里将空间复杂度降低到了O(n)，有兴趣的可以看看。

时间复杂度：O(mn)

空间复杂度：O(mn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution
{
public:
    bool isMatch(const char *s, const char *p)
    {
        int m = strlen(s), n = strlen(p);
        bool dp[m + 1][n + 1];
        
        dp[0][0] = true;
        for(int i = 0; i < m; ++ i)
            dp[i + 1][0] = false;
        for(int j = 0; j < n; ++ j)
            dp[0][j + 1] = '*' == p[j] && dp[0][j - 1];
        
        for(int i = 0; i < m; ++ i)
            for(int j = 0; j < n; ++ j)
            {
                if(p[j] != '*')
                    dp[i + 1][j + 1] = dp[i][j] && ('.' == p[j] || s[i] == p[j]);
                else
                    dp[i + 1][j + 1] = dp[i + 1][j - 1] || dp[i + 1][j] || 
                        dp[i][j + 1] && ('.' == p[j - 1] || s[i] == p[j - 1]);
            }
        
        return dp[m][n];
    }
};