正则表达式匹配

正则表达式匹配

题目链接:https://leetcode.com/problems/regular-expression-matching/description/

class Solution {
public:
    bool isMatch(string& s, string& p) {
        // 注意:不要添加如下代码
        // if(s.size() == 0 || p.size() == 0)
        //     return false;
        // 因为在如下case情况下,应该返回true,但是如果加上上面的代码,则返回false。因为.*可以匹配任意字符串,包括空字符串。
        // ""
        // ".*"
        return matchCore(s, 0, p, 0);
    }
    
    bool matchCore(string& s, int i, string& p, int j)
    {
        int s_len = s.size();
        int p_len = p.size();
        if(i == s_len && j == p_len)
            return true;
        if(i != s_len && j == p_len)
            return false;
        // 执行完上面的代码后,保证了访问p[j]不会溢出,但是访问s[i]还有可能溢出,因为存在这样的情况i==s_len, j != p_len
        if(j < p_len-1 && p[j+1] == '*')
        {
            if(i < s_len && (s[i] == p[j] || p[j] == '.'))
            {
                return matchCore(s, i, p, j+2) || matchCore(s, i+1, p, j)
                    || matchCore(s, i+1, p, j+2);
            }
            else
            {
                return matchCore(s, i, p, j+2);
            }
        }
        else
        {
            if(i < s_len && (s[i] == p[j] || p[j] == '.'))
                return matchCore(s, i+1, p, j+1);
            else
                return false;
        }
        return false;
    }
};

上面的方法运行时间比较长,在别人的答案里看到了一个使用DP方法的答案,拿过来膜拜一下。暂时还没有解读。

4ms的代码如下:

static const auto __ = []()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	return nullptr;
}();
class Solution {
public:
	bool isMatch(string s, string p) {	
		if (s.empty()&&p.empty()) return true;
		if ( p.empty()) return false;
		vector<vector<bool>> dp(s.size() + 1, vector<bool>(p.size() + 1, false));
		dp[0][0] = true;
		for (int i = 0; i < s.size() + 1; ++i)
		{
			
			for (int j = 1; j < p.size() + 1; ++j)
			{
				if (i>0&&(s[i-1] == p[j-1] || p[j-1] == '.')) dp[i][j] = (dp[i - 1][j - 1]?true:dp[i][j]);
				if (p[j-1] == '*')
				{
					if (i>0&&(p[j - 1-1] == s[i-1]|| p[j - 1 - 1] == '.'))
					{
						dp[i][j] = dp[i][j - 1] || dp[i - 1][j]||dp[i][j-2];
					}
					else
					{
						dp[i][j] = dp[i][j - 2];
					}
				}
			}
		}
		return dp[s.size()][p.size()];		
	}
};

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

19 − 8 =

39 − = 30