Алгоритм(1) — сопоставление регулярных выражений и сопоставление подстановочных знаков

LeetCode10 — сопоставление регулярных выражений

Есть два решения этой проблемы. Одно — рекурсивное, другое — динамическое программирование.

(1)Рекурсивный

class Solution {
public:
    bool isMatch(string s, string p) {
        if(p.empty()) return s.empty();
        bool firstMatch = (!s.empty() && (s[0] == p[0] || p[0] == '.'));
        if(p.length() >= 2 && p[1] == '*'){
            return isMatch(s, p.substr(2)) || (firstMatch && isMatch(s.substr(1), p));
        }
        else{
            return firstMatch && isMatch(s.substr(1),p.substr(1));
        }
        
    }
};

Однако это не эффективный способ решения проблемы. Его время выполнения составляет 128 мс.

(2)Динамическое программирование

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        vector<vector<bool>> dp(m+1, vector<bool> (n+1, false));
        dp[0][0] = true;
        for(int i=0; i <= m; i++){
            for(int j=1; j<=n; j++){
                if(p[j-1] == '*'){
                    dp[i][j] = (i>0 && dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.')) || dp[i][j-2];
                }else{
                    dp[i][j] = i>0 && dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.');
                }
            }
        }
        return dp[m][n];
    }
};

Это решение работает намного лучше, время выполнения которого составляет всего 12 мс.

LeetCode44-подстановочный знак соответствия

Есть также два вида решений: рекурсивное и динамическое программирование, однако рекурсивное занимает слишком много времени, чтобы получить результат за ограниченное время. Так что просто используйте динамическое программирование.

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.length(), n = p.length();
        vector<vector<bool>> dp(m+1, vector<bool> (n+1, false));
        dp[0][0] = true;
        for(int i=0; i<=m; i++){
            for(int j=1; j<=n; j++){
                if(p[j-1] == '*'){
                    //skip redundant *
                    if(p[j-2] == '*') dp[i][j] = dp[i][j-1];
                    else dp[i][j] = (i>0 && dp[i-1][j]) || (i>0 && dp[i-1][j-1]) || dp[i][j-1];
                }
                else{
                    dp[i][j] = i>0 && dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '?');
                }
            }
        }
        return dp[m][n];
    }
};