正则表达式匹配

1
2
3
4
5
6

输入：

s="aa"
p="a*"

输出:true

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    bool pre_match(string &s,string &p,int i,int j) {
        if(i<0 || j<0 || i>s.size() && j>p.size()) return false;
        return s[i] == p[j] || p[j] =='.';
    }
    bool isMatch(string s, string p) {
        int n =s.size()  , m = p.size()  ;
        //dp[i,j] , 前 i 个字符和 前 j 个字符是否匹配
        vector<vector<int>> dp(n+5,vector<int> (m+5));
        dp[0][0] = 1;
        for(int j=2;j<=m;++j)
        {
            dp[0][j] = p[j-1] =='*' && dp[0][j-2];
        }
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j) {
                if(p[j] =='*') {
                    dp[i+1][j+1] = dp[i+1][j-1] ||(  pre_match(s,p,i,j-1) && dp[i ][j+1]);
                }else 
                    dp[i+1][j+1] =  pre_match(s,p,i,j) && dp[i][j];
            }
        }
        
        
        return dp[n  ][m ];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
public:
    bool isMatch(string _s, string _p) {
        s = _s, p = _p;
        f = vector<vector<int>> (s.size()+1,vector<int>(p.size() +1,-1));
        return dfs(0,0);
    }
    string s,p;
    vector<vector<int>> f;
    bool dfs(int si,int pi) {
        if(f[si][pi] != -1) {
            return f[si][pi];
        }
        if(pi == p.size())
            return f[si][pi] = si == s.size();
        //pi 到达终点了， si也要同时到达终点
        bool pre_match = si < s.size() && (s[si] == p[pi] || p[pi] == '.');
        bool ans = false;
        if(pi+1<p.size() && p[pi+1] =='*' ) {
            // p[pi] 是否匹配 si + 1
            //或者 出现0 次，用 pi + 2 来匹配
            ans = dfs(si ,pi+2) || (pre_match && dfs(si + 1,pi)) ;
            
        }
        else {
            //不等于 *
            ans = pre_match && dfs(si+1,pi+1);
        }
        return f[si][pi] = ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param p string字符串 
     * @return bool布尔型
     */
    boolean[][]dp;
    char[] s1;
    char[] s2;
    public boolean isMatch (String s, String p) {
        if("*".) return true;
        // write code here
        int n = s.length(), m = p.length();
        if(n == 0 &&m == 0) return true;
        
        s1 = s.toCharArray();
        s2 = p.toCharArray();
        dp = new boolean[n+1][m+1];
        dp[0][0] = true;
        for(int i=1;i<=m;++i) {
            dp[0][i] = dp[0][i-1] && (s2[i-1] == '*');
        }
        for(int i=1;i<=n;++i) {
            for(int j=1;j<=m;++j) {
                char a = s1[i-1] , b= s2[j-1];
                if(a == b ) {
                    dp[i][j] |= dp[i-1][j-1];
                }else if(b == '?') {
                    dp[i][j] |= dp[i-1][j-1];
                   // System.out.println("" + i +","+ j +" ?= "+dp[i][j]);
                    
                }else if(b == '*') {
                    //                             b==?        b==""       b=* && 前一个也和b 匹配
                    dp[i][j] = dp[i][j] || dp[i-1][j-1] || dp[i][j-1] || dp[i-1][j];
                   // System.out.println("" + i +","+ j +" *= "+dp[i][j]);
                }else {
                    dp[i][j] = false;
                }
            }
        }
        /*
           case1: s[i] == p[j]   dp[i][j] = dp[i][j] || dp[i-1][j-1]
           case2: p[j] == '.'    dp[i][j] = dp[i][j] || (dp[i-1][j-1])
           case3: p[j] == '?'    dp[i][j] = dp[i][j] || dp[i-1][j]
        */
       //return match(0,0,n,m);
  
        return dp[n][m];
        
    }
    /*
    boolean match(int l,int r, int n,int m) {
        if(r>=n || m>=n) return false;
        char s = s1[l], p = s2[r];
        if (s == p || p == '.' || p == '?') {
            if(l == n-1 &&  r  == m-1) {
                return s==p || p == '?' || p == '*';
            }
            //这种属于匹配到的字符了
            if(s == p) {
                //匹配就往下面走
                return match(l+1,r+1,n,m);
            }
            if(p == '?') {
                return match(l+1,r+1,n,m);
            }
            if(p == '*') {
                //前面l 个 和  * 前面的匹配了
                //case1: * 作用等于 ?
                //case2: * 作用等于空串
                //case3: * 作用匹配 N多个字符
                return match(l+1,r+1,n,m) /* 作用等于 ? */ 
                    || match(l+1,r,n,m) /* ? 匹配 0 - N个字符 */
                      || match(l,r+1,n,m);
            }
        }
        
        return false;
    }
    
    */
    
    
}