本文共 1533 字，大约阅读时间需要 5 分钟。

实现支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符。'*' 匹配零个或多个前面的元素。匹配应该覆盖整个输入字符串（不是部分字符串）。函数:bool isMatch(const char *s, const char *p)例子:isMatch("aa","a") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "a*") → trueisMatch("aa", ".*") → trueisMatch("ab", ".*") → trueisMatch("aab", "c*a*b") → true

对于题目稍微解释一下： *必须和前面的字符组合起来用，表示0~n个该字符 ，因此P的第一个字符不可以是*

采用动态规划来做：

dp[i][j]表示s的前i个字符和p的前j个字符的匹配情况，设~为匹配符号，设s=s'n, p=p'mq

1、当p[j-1]！=‘*’时：

只有n~q，即：n = q || q= '.'时，

s和p才有可能匹配：dp[i][j] = dp[i - 1][j - 1];

2、当p[j-1] ==‘*’时，

如果n!~m, 则mq相当于0个字符，dp[i][j]=dp[i][j - 2]

如果n~m, 则mq可以相当于0或1或多个字符

    当mq相当于0个字符时，判断s'n与p'是否匹配，即 dp[i][j] =dp[i][j - 2]

    当mq相当于1个字符时，判断s'与p'是否匹配，dp[i][j] =dp[i-1][j - 2]

    当mq相当于多个字符时，判断s'与p'mq是否匹配，dp[i][j] =dp[i-1][j ]

以上只要有一种情况匹配上就说明匹配

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

转载地址：http://zhabi.baihongyu.com/