​leetcode算法题第10题：正则表达式匹配​

leetcode算法题第10题&＃xff1a;正则表达式匹配

题目&＃xff1a;

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

&＃39;.&＃39; 匹配任意单个字符
&＃39;*&＃39; 匹配零个或多个前面的那一个元素
所谓匹配&＃xff0c;是要涵盖 整个 字符串 s的&＃xff0c;而不是部分字符串。

解题思路&＃xff1a;动态规划法

我们用 f[i][j] 表示 s 的前 i 个字符与 p 中的前 j个字符是否能够匹配。在进行状态转移时&＃xff0c;我们考虑 p 的第 j 个字符的匹配情况&＃xff1a;

1.当第j个字符不是&＃39;*&＃39;时&＃xff0c;则要匹配s[i]和p[j]的情况&＃xff0c;如果不相等&＃xff0c;则s和p一定不匹配。如果s[i]&＃61;&＃61;p[j]&＃xff0c;则要转移到对前i-1和j-1的字符匹配情况&＃xff0c;所以此时有状态转移方程如下:

如下图也能很好的展示动态规划过程&＃xff0c;第一行和第一列表示的是动态矩阵的初始值。

代码&＃xff1a;