問題來源

https://leetcode.com/problems/regular-expression-matching/

遞歸方法

class Solution {
public:
    bool isMatch(string s, string p) {
        if(p.size() == 0) return s.size() == 0;
        bool first_match = (s[0] == p[0] or p[0]=='.');
        if(p[1]=='*') return isMatch(s, p.substr(2, p.size()-2)) or (first_match and s.size() > 0 and isMatch(s.substr(1, s.size()-1), p));
        else return first_match and s.size() > 0 and isMatch(s.substr(1, s.size()-1), p.substr(1, p.size()-1));
    }   
};

復(fù)雜度分析

令和分別表示匹配串的長(zhǎng)度和模式串的長(zhǎng)度。
在最壞情況下，調(diào)用match(text[i:], pattern[2j:]的次數(shù)最多會(huì)達(dá)到(組合數(shù))次。參考代碼，i和j每次前進(jìn)一步，均需要調(diào)用一次match。而到達(dá)text[i:], pattern[2j:]一共存在種可能性，最壞情況下每種情況均需要調(diào)用match(text[i:], pattern[2j:]。

改進(jìn)思路

遞歸方法速度較慢的核心問題是存在重復(fù)調(diào)用的問題，如果我們記錄下每次調(diào)用的結(jié)果，就可以將遞歸轉(zhuǎn)換為動(dòng)態(tài)規(guī)劃。

動(dòng)態(tài)規(guī)劃解法

自頂向下（遞歸）

class Solution {
public:
    bool dp(int i, int j, int* memo, string s, string p)
    {
        if(memo[j + i*(p.size()+1)] != -1)
        {
            return memo[j + i*(p.size()+1)];
        }
        else
        {
            if(j == p.size())
            {
                if(i == s.size())
                {
                    memo[j + i*(p.size()+1)] = 1;
                    return 1;
                }
                else
                {
                    memo[j + i*(p.size()+1)] = 0;
                    return 0;                 
                }
            }
            bool first_match = (i < s.size() and (s[i] == p[j] or p[j] == '.'));
            if(p[j+1] == '*') 
            {
                bool result = dp(i, j+2, memo, s, p) or (first_match and dp(i+1, j, memo, s, p));
                memo[j + i*(p.size()+1)] = result;
                return result;
            }
            else
            {
                bool result = (first_match and dp(i + 1, j + 1, memo, s, p));
                memo[j + i * (p.size() + 1)] = result;
                return result;
            }
        }
    }
    
    bool isMatch(string s, string p)
    {
        int memo[(s.size() + 1)*(p.size() + 1)];
        for(int i=0;i < (s.size() + 1)*(p.size() + 1);i++) memo[i]=-1;
        bool result = dp(0, 0, memo, s, p);
        return result;
    }
};

自底向上（迭代，尾遞歸轉(zhuǎn)迭代）

class Solution {
public:
    bool isMatch(string s, string p)
    {
        int dp[(s.size() + 1)*(p.size() + 1)];
        for(int i=0;i < (s.size() + 1)*(p.size() + 1);i++) dp[i]=0;
        dp[(s.size() + 1)*(p.size() + 1)-1] = 1;
        for(int i = s.size();i>=0;i--){
            for(int j = p.size() - 1;j>=0;j--)
            {
                bool first_match = i < s.size() and (s[i] == p[j] or p[j] == '.');
                if(p[j + 1] == '*')
                {
                    dp[j + i * (p.size() + 1)] = dp[j + 2 + i * (p.size() + 1)] or (first_match and dp[j + (i + 1) * (p.size() + 1)]);
                }
                else
                {
                    dp[j + i * (p.size() + 1)] = (first_match and dp[j + 1 + (i + 1) * (p.size() + 1)]);
                }
            }
        }
        return dp[0];
    }
};

復(fù)雜度分析

最多計(jì)算dp的容量大小T*P次， 故時(shí)間復(fù)雜度