StringMatching

发表于 分类于

题目描述[原题链接][https://www.acwing.com/problem/content/description/28/]

请实现一个函数用来匹配包括'.'和'*'的正则表达式。

模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。

在本题中，匹配是指字符串的所有字符匹配整个模式。

例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配。

样例

1
2
3
4
5
6
输入：

s="aa"
p="a*"

输出:true

算法描述

实力有限，有待加强啊

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool isMatch(string s, string p) {
        if(p.empty())return s.empty();
        bool frist = !s.empty()&&(s[0] == p[0]||p[0]=='.');
        if(p.length() >= 2 && p[1] == '*'){
            return isMatch(s,p.substr(2))||(frist&&isMatch(s.substr(1),p));
        }else {
            return frist&&isMatch(s.substr(1),p.substr(1));
        }
    }
};

Java代码

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
class Solution {
    
    int[][] f;
    int n,m;
    
    public boolean isMatch(String s, String p) {
        n=s.length();
        m=p.length();
        f=new int[n+1][m+1];
        f[n][m]=1;
        dp(0,0,s,p);
        return dp(0,0,s,p)==1;
    }
    
    int dp(int x,int y,String s,String p){
        if(f[x][y]!=0)return f[x][y];
        if(y==m){
            if(x==n)f[x][y]=1;
            else f[x][y]=0;
            return f[x][y];
        }
        boolean firstMatch = x<n&&(s.charAt(x)==p.charAt(y)||p.charAt(y)=='.');
        boolean ans;
        if(y+1<m&&p.charAt(y+1)=='*'){
            ans=dp(x,y+2,s,p)==1||firstMatch&&dp(x+1,y,s,p)==1;
        }
        else {
            ans = firstMatch&&dp(x+1,y+1,s,p)==1;
        }
        if(ans)
        f[x][y]=1;
        else f[x][y]=0;
        return f[x][y];
    }

    
}