正则表达式的匹配

class Solution {
public:
    bool isMatch(const char *s,const char *p) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function    
        if (*p == '') return *s == '';
        if (*(p+1) == '*') // 模式串的下一个字符是'*'
        {
            while(*p == *s || (*p == '.' && *s != ''))
            {
                //字符串与模式串匹配0/1/2...个字符的情况
                if (isMatch(s++,p+2))
                    return true;
            }
            // 字符串与模式串不能匹配
            return isMatch(s,p+2);
        }
        else
        {
            if (*p == *s || (*p == '.' && *s != ''))
                return isMatch(s+1,p+1);
            return false;
        }
    }
};

核心思路是一个动态规划，dp[i][j]表示字串 s[i...len(s)],p[j...len(p)] 是否可以匹配。

状态转移方程如下： dp[i][j] = c1. p[j+1] != '*'时 if s[i] == p[j] dp[i][j] = dp[i+1][j+1] else dp[i][j] = false c2 p[j+1] == '*'时 (这个情况下，要扩展 *,dp[i][j] 从拓展的情况下，选择一个是真的结果） if( s[i] == p[j] || p[j] == '.' && (*s) != 0) 当s[i] 和 p[j] 一样的时候，例如 aba,a*b这个时候，i = 0,j = 0,自然可以匹配a a 如果p[j] == . 因为他可以匹配任何字符，所以和相等关系有基本一样的方式。 并且每一步匹配都要递增 i 的值，如果有成立的，则返回true，否则到匹配终了，返回通配符匹配完成后的结果。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!