leetcode题解之正则表达式匹配

leetcode第10题，之前提交做过，今天再看到有点乱，写下来记录下；
题目：正则匹配，不过pattern串中只有小写字母，和'.'外加'*'。
其实这道题目如果没有'*'直接一路匹配过去就好了，不用想太多；但是题目中有这个，就得想办法解决了。'*'在正则中表示匹配0个或多个前一个字符，这样的话，如果当前是'*'就得知道前一个字符，这就引导我们去做从后向前的字符串匹配了，具体代码如下：

bool isMatch(string s, string p){
    int s_len=s.length(), p_len=p.length();
    // dp[i][j] 表示s[i:], p[j:]能否完全匹配
    vector<vector<bool> > dp(s_len+1, vector<bool>(p_len+1, false));
    dp[s_len][p_len]=true;// 空匹配为真
    // pattern 串有可能匹配空，所以
    for(int i=s_len; i>=0; i--){
        for(int j=p_len-1; j>=0; j--){
            // 先判断当前是否能够匹配
            bool is_match = i<s_len&&(s[i]==p[j]||p[j]=='.');
            if(j+1<p_len && p[j+1]=='*'){
                // 匹配0个或者多个(多个的时候用到了“后向迭代思路”)
                dp[i][j]=dp[i][j+2]||(is_match && dp[i+1][j]);
            }else{
                dp[i][j]=is_match && dp[i+1][j+1];
            }
        }
    }
    return dp[0][0];
}