剑指 Offer 19. 正则表达式匹配

请实现一个函数用来匹配包含’. ‘和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但与”aa.a”和”ab*a”均不匹配。

❤❤递归

思路

同时遍历正则与字符串，取正则当前cur和后一位next和字符串当前scur，并以next的值是否等于*作为判断

• next=='*'

若scur==cur || cur=='.',由于cur*匹配0次或多次，故有两个选择：

  1. 跳过cur *
  1. 使用cur *

• next!='*'

若scur==cur || cur=='.'，递归；否则返回false;

对于递归终止条件：
当字符串长度0时，若正则余下不能自我匹配到0，则返回false，否则返回true;
当字符串长度不为0，且正则长度为0，则false;

算法

• 递归条件
• 递归终止条件

• 剪枝

  实现

  bool _isMatch_aux(string s,string p){
    int m=s.size(),n=p.size();
    if(m==0){
        if(n%2==1) return false;
        for(int i=1;i<n;i+=2){
            if(p[i]!='*') return false;
        }
        return true;
    }
    if(n==0) return false;
    char s_begin=s[0];
    char p_begin=p[0];
    char p_next=' ';
    if(n>1) {
        p_next=p[1];
    }
    if(p_next!='*'){
        if(s_begin==p_begin || p_begin=='.'){
            return _isMatch_aux(s.substr(1),p.substr(1));
        }
        else return false;
    }
    else{
        if(s_begin==p_begin || p_begin=='.'){
            return  _isMatch_aux(s.substr(1),p) || _isMatch_aux(s,p.substr(2));
        }
        else{
            return _isMatch_aux(s,p.substr(2));
        }
    }
  }

  复杂度分析

• 时间复杂度:不太会分析

• 空间复杂度:

❤❤❤动态规划

思路

假设字符串为A，长度为n,模式串为B，长度为m，关注正则表达式后一个字符是什么，有三种情况，正常字符、*、.

1. 如果B后一个字符是正常字符，那就看A[i]和B[j]是否相等（B[j]==’.’时也相等），不等就不不匹配，相等则比较A[i+1..]和B[j+1…]
2. 如果B后一个字符是*，则B[j]可使用0次或多次

• 0次：继续比较A[i+1…]和B[j+2…]

• 多次:继续比较A[i+1…]和B[j]

  算法

• 状态矩阵：

f[i][j]代表A的前i个和B的前j个能否匹配

• 针对思路1，有f[i][j]=f[i-1][j-1]+A[i]==b[j]
• 针对思路2，
  • 不看：f[i][j]=f[i][j-2]
  • 看：f[i][j]=f[i-1][j]
    • 状态转移方程如下：

• 初始状态：

f[0][0]=true;显然空串和空正则匹配；
非空串和空正则比不匹配，f[1][0]=…f[n][0]=false;

实现

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

复杂度分析

• 时间复杂度:
• 空间复杂度:

题目标题难度划分

算法掌握难度程度划分