字符串正则匹配(递归/DP)

Wildcard-Matching & Regular Expression Matching

Wildcard-Matching中?匹配任意一个字符，*匹配任意长度字符串包括空字符串

方法一：记录*的位置，分别考虑*匹配空，匹配一个，匹配两个，三个...

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

         int sStar=-,pStar=-;

         int i=,j=;

         for(i=;i<strlen(s);)//不考虑p字符串长 s=''aa'', p=''a''

         {

             if(p[j]=='*')

             {

                 sStar=i;

                 pStar=j;

                 j++;

             }

             else if(p[j]==s[i]||p[j]=='?')

             {

                 i++;

                 j++;

             }

             else if(sStar>=)//没有匹配但之前记录sStar了

             {

                 i = ++sStar;

                 j = pStar+;

             }

             else return false;

         }

         while(p[j]=='*')j++;

         return j==strlen(p);

     }

方法二：DP dp[i][j]=1表示s[0:i)与p[0:j)匹配，状态转移以*划分两种情况，包含*又有两种状态转移，根据无后效性可知，有匹配空和匹配s中的一个字符这两种

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

         int dp[strlen(s)+][strlen(p)+];

         memset(dp,,sizeof(dp));

         dp[][]=;

         for(int j=;j<=strlen(p);j++)

         {

             if(p[j-]=='*')

                 dp[][j]=dp[][j-];

         }

         for(int i=;i<=strlen(s);i++)

             for(int j=;j<=strlen(p);j++)

             {

                 if(p[j-]=='*')

                     dp[i][j]=dp[i][j-]||dp[i-][j];

                 else

                     dp[i][j]=dp[i-][j-]&&(s[i-]==p[j-]||p[j-]=='?');

             }

         return dp[strlen(s)][strlen(p)];

     }

Regular Expression Matching

*表示*之前的字符可以有0个，1个或是多个

方法一：递归

注意不应该先判原串s为空，p为*也可以

p[1]==* 需要匹配s中的一个字符时，注意p不能去掉首字符，因为*号前面的字符可以有无限个；

 bool isMatch(string s, string p)

 {

     if(p.empty())return s.empty();

     if(p.size()>&&p[]=='*')

         return isMatch(s,p.substr())||(!s.empty() && (s[] == p[] || p[] == '.') && isMatch(s.substr(),p));

     else

         return !s.empty()&& (p[]==s[]||p[]=='?') && isMatch(s.substr(),p.substr());

 }

方法二：DP dp[i][j]=1表示s[0:i)与p[0:j)匹配

1. P[i][j] = P[i - 1][j - 1], if p[j - 1] != '*' && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
2. P[i][j] = P[i][j - 2], if p[j - 1] == '*' and the pattern repeats for 0 times;
3. P[i][j] = P[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'), if p[j - 1] == '*' and the pattern repeats for at least 1

 bool isMatch(string s, string p) {

     int m = s.size(), n = p.size();

     int dp[m+][n+];

     memset(dp,,sizeof(dp));

     dp[][] = ;

     for (int i = ; i <= m; ++i) {

         for (int j = ; j <= n; ++j) {

             if (j >  && p[j - ] == '*') {

                 dp[i][j] = dp[i][j - ] || (i >  && (s[i - ] == p[j - ] || p[j - ] == '.') && dp[i - ][j]);

             } else {

                 dp[i][j] = i >  && dp[i - ][j - ] && (s[i - ] == p[j - ] || p[j - ] == '.');

             }

         }

     }

     return dp[m][n];

 }

参考自：Grandyang

巴特西

字符串正则匹配(递归/DP)

最新文章

热门文章