10. Regular Expression Matching 正则表达式匹配

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
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

Difficulty: Hard

这道题和剑指offer 52题一样,正则表达式匹配.,*

分析1

剑指offer 52题的解法

如果模式串此时是’.‘,那么只需要模式串匹配串都往后移动一个位置

如果现在这位的字符能匹配且模式串的下一位是*,我们则需要分情况讨论

  • 匹配串往后移动1位,模式串跳过'*'
  • 匹配串往后移动1位,模式串不动
  • 匹配串不动,模式串跳过'*'
class Solution {
public:
   bool isMatch(string s, string p) {
        const char* str = s.c_str();
        const char* pattern = p.c_str();
        return match2(str, pattern);
    }
    
    bool match2(const char* str,const char* pattern)
    {
        if (str==NULL||pattern==NULL) return false;
        if (*str=='\0'&&*pattern=='\0') return true;
        if (*str!='\0'&&*pattern=='\0') return false;
        
        if (*(pattern+1)=='*')
        {
            if (*str==*pattern||(*str!='\0'&&*pattern=='.'))
                return match2(str+1, pattern+2)||match2(str+1, pattern)||match2(str, pattern+2);
            return match2(str, pattern+2);
        }
        if (*str==*pattern || (*pattern=='.'&&*str!='\0'))
            return match2(str+1, pattern+1);
        return false;
    }
};

分析2

也可以用Dynamic Programming来解.参考jianchao.li.fighter的解法.定义P[i][j]表示s[0..i)p[0..j)是否匹配.分析可得下面的方程

  • P[i][j] = P[i-1][j-1],if p[j-1] != '*' && (s[i-1] == p[j-1] || p[j-1] == '.');
  • P[i][j] = P[i][j-2],if p[j-1]=='*' and the pattern repeats for 0 times;
  • 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 times.

上面P[i][j],i的取值是从0到s.size(),j的取值是是从0到p.size().s的取值范围是0到s.size()-1.p的取值范围是0到p.size()-1.举个例子

s = "ab";
p = "ab";
P[0][0] = s[0,0)j[0,0) = true
P[1][1] = s[0,1)p[0,1) = s[0]p[0] = ('a'=='a') = true
class Solution {
public:
    
  bool isMatch(string s, string p)
  {
      int m = s.size(), n = p.size();
        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];
  }
 
comments powered by Disqus