LeetCode:Regular Expression Matc

问题来源

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));
    }   
};

复杂度分析

令和分别表示匹配串的长度和模式串的长度。
在最坏情况下，调用match(text[i:], pattern[2j:]的次数最多会达到(组合数)次。参考代码，i和j每次前进一步，均需要调用一次match。而到达text[i:], pattern[2j:]一共存在种可能性，最坏情况下每种情况均需要调用match(text[i:], pattern[2j:]。

改进思路

递归方法速度较慢的核心问题是存在重复调用的问题，如果我们记录下每次调用的结果，就可以将递归转换为动态规划。

动态规划解法

自顶向下（递归）

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;
    }
};

自底向上（迭代，尾递归转迭代）

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];
    }
};

复杂度分析

最多计算dp的容量大小T*P次， 故时间复杂度