算法沉淀——动态规划之两个数组的 dp（下）（leetcode真题剖析）

算法沉淀——动态规划之两个数组的 dp

• 01.正则表达式匹配
• 02.交错字符串
• 03.两个字符串的最小ASCII删除和
• 04.最长重复子数组

  01.正则表达式匹配

  题目链接：https://leetcode.cn/problems/regular-expression-matching/

  给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

  • '.' 匹配任意单个字符
  • '*' 匹配零个或多个前面的那一个元素

    所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

    示例 1：

    输入：s = "aa", p = "a"
    输出：false
    解释："a" 无法匹配 "aa" 整个字符串。
    

    示例 2:

    
    （图片来源网络，侵删）

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

    示例 3：

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

    提示：

    • 1 public: bool isMatch(string s, string p) { int m=s.size(),n=p.size(); s=" "+s,p=" "+p; vector if(p[j]=='*') dp[i][j]=dp[i][j-2]||(p[j-1]=='.'||p[j-1]==s[i])&&dp[i-1][j]; else dp[i][j]=(p[j]==s[i]||p[j]=='.')&&dp[i-1][j-1]; } return dp[m][n]; } }; public: bool isInterleave(string s1, string s2, string s3) { int m=s1.size(),n=s2.size(); if(s3.size()!=m+n) return false; s1=" "+s1,s2=" "+s2,s3=" "+s3; vector public: int minimumDeleteSum(string s1, string s2) { int m=s1.size(),n=s2.size(); vector dp[i][j]=max(dp[i][j-1],dp[i-1][j]); if(s1[i-1]==s2[j-1]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+s1[i-1]); } int sum=0; for(auto s:s1) sum+=s; for(auto s:s2) sum+=s; return sum-dp[m][n]*2; } }; public: int findLength(vector int m=nums1.size(),n=nums2.size(); vector