LeetCode 10

一、问题描述

Description:

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)

For 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

实现正则表达式匹配，匹配字符'.'和'*'：

'.'匹配任何单个的字符。
'*'前面的字符重复 ≥ 0 次。

二、解题报告

对于上面的 example，可能有人会对isMatch("ab", ".*") → true产生疑问，我的理解是*可以将.重复多次，而.可以表示任意单个字符，所以结果是正确的。

这里提供两种解法：递归法和动态规划法

1. 递归法

使用递归进行判断时，总体上可以分成两种情况：一种是以'*'开头的，另一种不是。

class Solution {
public:
    bool isMatch(string s, string p) {
        int lens = s.length();
        int lenp = p.length();
        if(lenp == 0)
            return lens == 0;

        if(lenp==1 || p[1]!='*')   // 第二个字符不是'*'
        {
            if(lens<1 || (s[0]!=p[0] && p[0]!='.'))
                return false;
            return isMatch(s.substr(1,lens-1), p.substr(1,lenp-1));
        }
        else                       // 第二个字符是'*'
        {
            int i=-1;
            while(i<lens && (i<0 || p[0]=='.' || p[0]==s[i]))
            {
                if(isMatch(s.substr(i+1,lens-i-1), p.substr(2,lenp-2)))
                    return true;
                ++i;
            }
            return false;
        }
    }
};

2. 动态规划法

dp[i][j]表示字串s[i...len(s)] 与 p[j...len(p)]是否可以匹配。

class Solution {
public:
    bool isMatch(string s, string p) {
        int ls = s.length();
        int lp = p.length();
        vector<vector<bool>> dp(ls+1, vector<bool>(lp+1, false));

        dp[0][0] = true;   // 初始化
        for(int i = 1; i < lp && p[i] == '*'; i+=2){
            dp[0][i+1] = true;
        }

        for(int i = 1; i <= ls; ++i){
            for(int j = 1; j <= lp; ++j){
                if(p[j-1] == '.' || p[j-1] == s[i-1])
                    dp[i][j] = dp[i-1][j-1];
                else if(j > 1 && p[j-1] == '*')
                    dp[i][j] = dp[i][j-2] || (dp[i-1][j] && (p[j-2] == '.' || s[i-1] == p[j-2]));   // .*
            }
        }
        return dp[ls][lp];
    }
};

LeetCode答案源代码：https://github.com/SongLee24/LeetCode