Mickey's Blog ·

【leetCode】正则匹配DP解法

了解完了动态规划的概念,也做了一道实践的问题,现在我们回到这道题来看,根据这个作者的答案,他先构建了一个二维数组,你们可以理解为一个表格

无标题.png

首先构建表格用false(红)填充 然后定义左上角位置为true(绿)双循环左侧代表每列代表一个s字符,每行代表一个p匹配符,双重循环最终判断右下角是否是绿色来判断是否匹配成功。举一个成功匹配的例子

s=abccg

p=abcdg

无标题.png

原解法传送门: https://discuss.leetcode.com/topic/17852/9-lines-16ms-c-dp-solutions-with-explanations