（leetcode算法题）10. 正则表达式匹配

10. 正则表达式匹配 - 力扣（LeetCode）

此题的要求一个字符串 s 和一个字符规律 p之间支持 '.' 和 '*' 的正则表达式匹配

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

保证每次出现字符 * 时，前面都匹配到有效的字符 也就是说p中所有的 * 字符前的那个字符只会是 . 或者字母
示例 1：       输入：s = "a", p = ".*"        输出：true
示例 2：       输入：s = "aab", p = "c*a*b"        输出：true
示例 3：       输入：s = "a", p = "a*"        输出：true
示例 4：       输入：s = "a", p = ".*a"        输出：true

根据经验和题目要求，两个字符串的关系可以考虑二维dp表，

能够解决的leetcode中的1143. 最长公共子序列、72. 编辑距离中dp的建立相似，

dp[i][j]表示p[0.j]区间内的子串是否能够匹配s[0,i]区间内的子串

状态转移方程：根据 p 切出来的子串中的最后一个字符来分情况讨论，这种按两个子串的最后一个字符的取值来分情况讨论的方式，也是推导状态转移方程的普遍步骤，

记记dp[i][j] = x; dp[i - 1][j] = y; dp[i][j - 2] = z dp[i - 1][j - 1] = w

则当p[j - 1] 为字母或者 点号时，

只用通过 w 和 (s[i - 1] == p[j - 1] || p[j - 1] == '.')这个表达式是否为真就能更新dp[i][j]

当p[j - 1] 为星号时，

只用通过y 和 z 和(s[i - 1] == p[j - 2] || p[j - 2] == '.') 这个表达式是否为真就能更新dp[i][j]

图一 

读者可能会问了，道理我都懂，为什么使用了dp[i][j - 2] 来更新dp[i][j]，而dp[i][j - 1]却没有使用？

 让我们来看看图一中  出现p[j - 1] == '*' && p[j - 2] == '.' 的情况

此时可以选择产生空串，或者将产生一个点号、两个点号，等等

那么dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] || ...  dp[i - m][j - 2] || ...                                          (1)

令i = u - 1

则有dp[u - 1][j] = dp[u - 1][j - 2] || dp[u - 2][j - 2] || ... dp[u - m - 1][j - 2] || ...                      (2)

观察可知，可将（2）代入（1）中得到

dp[i][j] = dp[i][j - 2] || dp[i - 1][j]

让我们再来看看图一中  出现p[j - 1] == '*' && p[j - 2] != '.' 的情况

此时可以选择产生空串，或者将产生一个p[j - 1]、两个p[j - 1]，等等

那么

dp[i][j] = dp[i][j - 2] || ((s[i -1] == p[j - 2]) && (dp[i - 1][j - 2])) || ... ((s[i - m] == p[j - 2]) && dp[i - m][j - 2] ) || ...                                                                                                                     (3)

令i = v - 1

则有dp[v - 1][j] = dp[v - 1][j - 2] || ( (s[v - 2] == p[j - 2]) && (dp[v - 2][j - 2]) ) || ... ( (s[v - m - 1] == p[j - 2]) && (dp[v - m - 1][j - 2]) ) || ...                                                                            (4)

观察可知，可将（4）代入（3）中，然后经过一些列的推导(具体步骤略)，可以得到

dp[i][j] = dp[i][j - 2] || ( (s[i -1] == p[j - 2]) && dp[i - 1][j])

知道这道题为什么用到了dp[i][j - 2]了吧，但是还有一个很重要的问题，就是在编写这道题的程序的时候，可以给这个dp表多加一行，多加一列，所以

上面在访问原数组是 s[i - 1] 代表的就是第 i 个元素

那么多加的这一行/列是否可以赋予这个题目场景下的具体意义呢？

多加的一行，可以赋予dp[0][j] 一个意义，其意义就是s作为一个空串，匹配p[0, j]

如果在这种定义下，dp[0][j]要想为true，j 和 p[j] 必须满足以下条件才能保证匹配

dp[0, j] 是形如 {{非星号}{星号} {非星号}{星号} {非星号}{星号} {非星号}{星号}}

而dp[i][0] 此时只有在dp[0][0]处会为true

class Solution {
public:bool isMatch(string s, string p) {int len1 = s.size();int len2 = p.size();vector<vector<bool>> dp(len1 + 1, vector<bool>(len2 + 1, false));dp[0][0] = true;for(int j = 2; j <= len2; j += 2){if(p[j - 1] == '*'){dp[0][j] = true;}else{break;}}for(int i = 1; i <= len1; ++i){for(int j = 1; j <= len2; ++j){if(p[j - 1] != '*'){dp[i][j] = ((p[j - 1] == s[i - 1] || p[j - 1] == '.') && dp[i - 1][j - 1] == true);}else{dp[i][j] = ((dp[i][j - 2] == true) || ((p[j - 2] == s[i - 1] || p[j - 2] == '.') && (dp[i - 1][j] == true)));}}}return dp[len1][len2];}
};