正则表达式匹配

C 解法, 执行用时: 2ms, 内存消耗: 348KB, 提交时间: 2022-07-09

#include <stdio.h>

int main(){
    char str[1000];
    char pattern[1000];
    int n = 0,m = 0,i = 0,j = 0;
    scanf("%s",str);
    scanf("%s",pattern);
    n = strlen(str);
    m = strlen(pattern);
    int dp[n+1][m+1];
    for(i = 0; i <= n; i++){
        for(j = 0; j <= m; j++){
            dp[i][j] = 0;
        }
    }
    for(i = 0; i <= n; i++){
        for(j = 0; j <= m; j++){
            if(j == 0){
                dp[i][j] = (i == 0 ? 1 : 0);
            }
            else{
                if(pattern[j-1] != '*'){
                    if(i > 0 && (str[i-1] == pattern[j-1] || pattern[j-1] == '.')){
                        dp[i][j] = dp[i-1][j-1];
                    }
                }
                else{
                    if(j >= 2){
                        dp[i][j] |= dp[i][j-2];
                    }
                    if(i >= 1 && j >= 2 && (str[i-1] == pattern[j-2] || pattern[j-2] == '.')){
                        dp[i][j] |= dp[i-1][j];
                    }
                }
            }
        }
    }
    printf("%s",dp[n][m] == 1 ? "true" : "false");
//     printf("%d",dp[n][m]);
    return 0;
}

C++ 解法, 执行用时: 3ms, 内存消耗: 408KB, 提交时间: 2022-07-09

// #include<bits/stdc++.h>
#include <iostream>
#include <vector>

using namespace std;

int solve(string &s1, string &s2, int i, int j, vector<vector<int>> &dp);
int solve3(string &s1, string &s2);

int main(){
    string s1, s2;
    cin >> s1;
    cin >> s2;
    vector<vector<int>> dp(s1.size(), vector<int>(s2.size(),-1));
    int flag = solve(s1,s2,s1.size()-1,s2.size()-1,dp);
    flag ? cout << "true" << endl : cout << "false" <<endl;
    return 0;
}

int solve(string &s1, string &s2, int i, int j, vector<vector<int>> &dp){
    
    if(i < 0 ){//贪婪匹配后，造成str被用完。
      //只需要剩下部分满足字母+*的组合就匹配成功
        int flag = 1;
        for(int l = 0; l <= j; l+=2){
            if (s2[l] != '*' && s2[l+1] == '*')continue;
            else flag = 0;
        }
        return flag;
    }
    if(dp[i][j] != -1) return dp[i][j];
    if(i == 0 && j == 0){//两边只剩一个点的匹配，'.'可以匹配任何字符，要么两边为同一个字符。
        if(s2[j] == '.' || s2[j] == s1[i]) dp[i][j] = 1;
        else dp[i][j] = 0;
    }
    else{//当前字符匹配成功后，结果只和前值有关
        if(s1[i] == s2[j] || s2[j] == '.') dp[i][j] = solve(s1, s2, i-1, j-1, dp);
      //如果遇见‘*’号则进行贪婪匹配或者0次匹配。
        else if(s2[j] == '*') dp[i][j] = ((s1[i] == s2[j-1] || s2[j-1] == '.') && solve(s1, s2, i-1, j, dp)) || solve(s1, s2, i, j-2, dp);
        else dp[i][j] = 0;
    }
    return dp[i][j];
}

int solve3(string &s1, string &s2){//递推
    vector<vector<int>> dp(s1.size(), vector<int>(s2.size()));
    dp[0][0] = (s1[0] == s2[0] || s2[0] == '.');
    if(s2[1] == '.' || s2[1] == s1[0]) dp[0][1] = 1 - dp[0][0];
    else if(s2[1] == '*') dp[0][1] = dp[0][0];
    for(int j = 2; j < s2.size(); ++j){//初始化i=0行
        if( s2[j] =='.' || s2[j] == s1[0]) {
            int flag = 0;
            for(int l = 1; l <= j; l+= 2){
                if (s2[l] != '*'){
                    flag = 1;
                    break;
                }
            }
            dp[0][j] = 1 - flag;
        }
        else if(s2[j] == '*'){
            dp[0][j] = dp[0][j-1] || dp[0][j-2];
        }
    }
    for(int i = 1; i < s1.size(); ++i){//一般情况，遇到*号时，分匹配还是不匹配做出选择。
        for(int j = 1; j < s2.size(); ++j){
            if (s2[j] == '.' || s2[j] == s1[i]) dp[i][j] = dp[i-1][j-1];
            else if(s2[j] =='*') dp[i][j] = (dp[i-1][j] && (s2[j-1] == s1[i] || s2[j-1] == '.')) || (j>=2? dp[i][j-2]:0);
        }
    }
    return dp[s1.size()-1][s2.size()-1];
}

C 解法, 执行用时: 3ms, 内存消耗: 408KB, 提交时间: 2022-06-21

#include <stdio.h>
#include <stdbool.h>

int main() {
    char str[1001] = "", pattern[1001] = "";
    scanf("%s", str);
    scanf("%s", pattern);
    
    int sLen = strlen(str), pLen = strlen(pattern);
    bool **dp = (bool **)malloc(sizeof(bool *) * (sLen + 1));
    for (int i = 0; i < sLen + 1; i++) {
        dp[i] = (bool *)malloc(sizeof(bool) * (pLen + 1));
        memset(dp[i], 0, sizeof(bool) * (pLen + 1));
    }

    dp[0][0] = true;
    for (int j = 2; j < pLen + 1; j+=2) {
        if (pattern[j-1] == '*') {
            dp[0][j] = true;
        } else {
            break;
        }
    }
    for (int i = 1; i < sLen + 1; i++) {
        dp[i][0] = false;
        for (int j = 1; j < pLen + 1; j++) {
            if (pattern[j-1] == '.') {
                dp[i][j] = dp[i-1][j-1];
            } else if (pattern[j-1] == '*') {
                if (str[i-1] == pattern[j-2] || pattern[j-2] == '.') {
                    dp[i][j] = dp[i-1][j] || dp[i][j-2];
                } else {
                    dp[i][j] = dp[i][j-2];
                }
            } else {
                if (str[i-1] == pattern[j-1]) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = false;
                }
            }
        }
    }
    
    if (dp[sLen][pLen]) {
        printf("true");
    } else {
        printf("false");
    }
    
    for (int i = 0; i < sLen + 1; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return 0;
}

C++ 解法, 执行用时: 3ms, 内存消耗: 444KB, 提交时间: 2022-05-13

#include <iostream>
#include <cstring>
using namespace std;

#define MAX_N 1005



int main() {
    string s1, s2;
    cin >> s1 >> s2;
    int len1 = s1.size();
    int len2 = s2.size();
    bool dp[len1 + 1][len2 + 1];
    for (int i = 0; i <= len1; i++) {
        for (int j = 0; j <= len2; j++) 
            dp[i][j] = false;
    }
    
    // 初始化
    dp[0][0] = true;
    for (int i = 1; i <= len2; i++) {
        if (s2[i - 1] == '*') 
            dp[0][i] = dp[0][i - 2];  
    }
    
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (s2[j - 1] == '*') {
                if (s2[j - 2] == '.' || s2[j - 2] == s1[i - 1]) 
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1] || dp[i][j - 2];
                else 
                    dp[i][j] = dp[i][j - 2];
            } 
            else {
                if (s2[j - 1] == '.' || s2[j - 1] == s1[i - 1]) 
                    dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    
    if (dp[len1][len2]) 
        cout << "true" << endl;
    else 
        cout << "false" << endl;
    
    
    return 0;
}

C++ 解法, 执行用时: 3ms, 内存消耗: 452KB, 提交时间: 2022-03-31

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s,p;
    cin>>s>>p;
    vector<vector<bool>> dp(s.size()+1,vector<bool>(p.size()+1,false));
    dp[0][0]=true;
    for(int i=1;i<=p.size();i++){
        if(p[i-1]=='*')dp[0][i] = dp[0][i-2];
    }
    for(int i=1;i<=s.size();i++){
        for(int j=1;j<=p.size();j++){
            if(p[j-1]=='*'){
                if(p[j-2]=='.'||p[j-2]==s[i-1]){
                    dp[i][j] = dp[i-1][j] || dp[i][j-1] || dp[i][j-2];
                }
                else{
                    dp[i][j] = dp[i][j-2];
                }
            }
            else{
                if(p[j-1]=='.'||p[j-1]==s[i-1]){
                    dp[i][j] = dp[i-1][j-1];
                }
            }
        }
    }
    cout<<(dp[s.size()][p.size()]?"true":"false");
    return 0;
}

详情