首页 > 代码库 > leetcode -10. Regular Expression Matching

leetcode -10. Regular Expression Matching

技术分享

三种情况:

“a” 对应"a",

"." 对应 "a"

"a*" 对应 “aa”

 

当p为空,s为空时可以匹配;

若p的第二个字符为*,第一情况为不匹配(b, a*b);从 (b,b)开始匹配

                                    第二种情况为匹配(a, a*); 首元素相同, 从( ,a*)开始匹配

若p的第二个字符不为*, 首字符必须要匹配, 再对首字符后的字符串匹配

recursive solution:

class Solution {
public:

    
    bool isMatch(string s, string p) {
        if(p.empty()) return s.empty();
      //  if(s.empty()) return p.empty();
       
        if(p[1]==*)
        {
            return (isMatch(s,p.substr(2))||((p[0]==s[0]||p[0]==.)&&!s.empty()&&isMatch(s.substr(1),p)));
           // if(p[0]==s[0]||p[0]==‘.‘&&!s.empty())
          //      return isMatch(s.substr(1),p);
          //  else
          //      return isMatch(s,p.substr(2));
        }
        else
        {
            if(p[0]==s[0]||p[0]==.&&!s.empty())
                return isMatch(s.substr(1),p.substr(1));
            else
                return false;
            //return (p[0]==s[0]||p[0]==‘.‘)&&!s.empty()&&isMatch(s.substr(1),p.substr(1));
        }
    }
    
    
};

 

DP solution:

定义如果  dp[i+1][j+1]匹配,当s[0-i]与p[0-j]匹配。

如果 p[j]!=‘*‘, dp[i][j]=dp[i-1][j-1] && s[i-1]==p[j-1];

如果p[j]==‘*‘, dp[i][j]==dp[i][j-2], 0times repeat

                      dp[i][j]==dp[i-1][j]&& (s[i - 1] == p[j - 2] || p[j - 2] == ‘.‘)the pattern repeats for at least 1 times.

 

leetcode -10. Regular Expression Matching