文章目录

1. 1. Regular Expression Matching

Regular Expression Matching

---

这道题目和之前的一道Wildcard-Matching问题类似，只是这次的含义变成了，可以匹配0个或多个号之前的元素，比如在字符串中出现了b*，表示可以出现0个b，1个b，2个b…

我采用的方法仍然是动态规划，输入是两个字符串s和p，设d[i][j]表示是s[0…i-1]和p[0…j-1]是否匹配。

那么

1. d[i][j] = d[i-1][j-1] && (p[i-1] == s[j-1] || p[i-1] = ‘.’) 这种情况是处理如果当p[i-1]不为’*’，那么d[i][j]的状态取决于两边字符串个去掉一个的状态和这两个去掉字符是否相同的与。

2. d[i][j] = d[i-2][j] 这种情况是处理当p[i-1]为’‘，如果’‘前元素忽略，则d[i][j]的状态取决于p字符串去掉*及其之前元素后的状态。

3. d[i][j] = d[i-1][j] && (p[i-2] == s[j-1] || p[i-2] == ‘.’) 这种情况是处理当p[i-1]为’‘，如果’‘前元素出现1次及其以上的情况，那么这时候还需要判断’*’前元素是否与s[j-1]相等。