题目地址:https://leetcode.com/problems/regular-expression-matching/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) 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我的代码:
class Solution { public: bool isMatch(string s, string p) { int n=s.size(),m=p.size(); if(m==0) return n==0; if(m==1) return n==1&&(p[0]=='.'||p[0]==s[0]); if(p[1]!='*'){ if(n==0) return false; if(p[0]=='.'||p[0]==s[0]) return isMatch(s.substr(1),p.substr(1)); else return false; } else{ if(p[0]=='.'){ for(int i=0;i<=n;i++) if(isMatch(s.substr(i),p.substr(2))) return true; return false; } else{ for(int i=0;i<=n;i++){ if(i>0&&s[i-1]!=p[0]) break; if(isMatch(s.substr(i),p.substr(2))) return true; } return false; } } } };解题思路： 使用递归，每次判断p和s第一个符号是否匹配， 这时有三种情况，第一种是p的长度小于2，那么不可能有*符号，直接判断即可，第二种是p的第二个符号不为*符号，同样直接判断第一个符号是否相同即可，第三种是p的第二个符号为*，这时情况就比较复杂。 对第三种情况，考虑p的第一个字符，当为字母时，分别判断p的前两个字符匹配s的前k个相同字符的情况即可（k从0开始，最大为连续与p0相同的字符个数），当为 ‘.’ 时,分别判断p的前2个字符与s的前任意个字符匹配时的情况即可。
利用同样的思想，可以使用dp，用dp[i][j]表示s的前i个字符与p的前j个字符是否匹配，复杂度O(nm)。
