☆打卡算法☆LeetCode 10、实现正则表达式匹配 算法解析

示例 1：
输入：s = "aa" p = "a"<br>
输出：false<br>
解析: "a" 无法匹配 "aa" 整个字符串。
复制代码

示例 2：
输入：s = "aa" p = "a*"
输出：true
解析：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
复制代码

示例 3：
输入： s = "ab" p = ".*"
输出： true
解释： ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
复制代码

示例 4：
输入：s = "aab" p = "c*a*b"
输出：true
解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
复制代码

public class Solution 
{
    public bool IsMatch(string s, string p) 
    {
        bool[,] dp = new bool[s.Length + 1, p.Length + 1];
        dp[s.Length, p.Length] = true;
        for (int i = s.Length; i >= 0; i--)
        {
            for (int j = p.Length - 1; j >= 0; j--)
            {
                bool first_match = (i < s.Length && (p[j] == s[i] || p[j] == '.'));
                if (j + 1 < p.Length && p[j + 1] == '*')
                {
                    dp[i, j] = dp[i, j + 2]    //A
                        || first_match && dp[i + 1, j]; //B
                }
                else
                {
                    dp[i, j] = first_match && dp[i + 1, j + 1]; // C
                }
            }
        }
        return dp[0, 0];
    }
}
复制代码