【动态规划】正则表达式匹配

描述：

‘.’表示任意一个字符，'*'表示它前面的字符可以出现任意次（包括0次）。匹配是指字符串中的所有字符匹配整个模式。函数原型为：

bool isMatch(const char *s,const char *p)

输入示例：

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

定义 P[i][j] = true表示s[0..i-1]与 p[0..j-1]匹配，false表示不匹配，则有

当p[j-1]!='*'时，只需要判断s[i-1]与p[j-1]是否匹配即可，即此时P[i][j] = P[i - 1][j - 1],if p[j - 1] != '*' && (s[i - 1] == p[j - 1] || p[j - 1] == '.');

当p[j-1]=='*'时，如果表示前面字符重复0次，则p[i][j]=p[i][j-2];如果表示前面字符至少重复一次，则需要判断s[i-1]和p[j-2]是否匹配即可，即P[i][j] = P[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.')

代码如下：

class Solution {
public:
    bool isMatch(string s,string p) {
        int m = s.length(),n = p.length(); 
        vector<vector<bool> > dp(m + 1,vector<bool> (n + 1,false));
        dp[0][0] = true;
        for (int i = 0; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (p[j - 1] == '*')
                    dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]);
                else dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
        return dp[m][n];
    }
};

（编辑：李大同）

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