10(Excellent)_Regular_Expression_Matching.cpp

//字符串模式匹配
//1） "."可以匹配任意一个字符
//2） "*"可以匹配零个或更多的前继字符（即模式串中"*"的前一个字符）
//思路，动态规划
//dp[i][j]表示s[i...len(s)-1]，p[j...len(p)]是否可以匹配
//对于dp[i][j]状态转移方程
//1） 如果p[j+1] != '*'，则前一个字符必须匹配才有dp[i][j]=dp[i+1][j+1]，即s[i]==p[j]或者p[j]=='.'&&s[i]!='\0'；否则返回false
//2） 如果p[j+1] == '*'，则有两种情况
//		1.前一个字符不匹配，直接返回dp[i][j+2]
//		2.前一个字符匹配，如果dp[i][j+2]为真也可以返回true，否则s++，继续判断字符是否匹配（因为*可以匹配多个前继字符）

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        if(*p=='\0')
			return *s=='\0';
		if(*(p+1) != '*') {
			//下一个字符不是"*"
			if(*s==*p || (*p=='.' && *s!='\0'))
				//因为"."必须匹配一个字符，所以如果p[0]=='.'，s[0]不能为终止符
				return isMatch(s+1, p+1);
			else
				return false;
		}
		else {
			//下一个字符是"*"
			while(*s==*p || (*p=='.' && *s!='\0')) {
				if(isMatch(s, p+2))
					//"*"可以匹配零个前继字符，所以可以跳过它和它的前继字符继续检查
					return true;
				s++;
			}
			//当遇到不匹配的，则必须从s的该位置继续检测，p则从"*"后面的位置开始
			return isMatch(s, p+2);
		}
    }
};