题目：正则表达式匹配
要求：给定一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
- ' . '匹配任意单个字符
- ' * '匹配零个或多个前面的那个一个元素
例如 ：
输入：
s = "aaa" p = "a" 输出：false 解释："a"无法匹配"aaa"整个字符串
s = "aaa" p = "a*" 输出：true
s = "ab" p = ".*" 输出：true
s = "aab" p = "c*a*b" 输出：true
s = "mississippi" p = "mis*is*p*." 输出：false
题解：
-
初始化一个长度为s.length()和p.length()的二维布尔数组match
-
将match[0][0]设置为true
-
初始化该数组中的值，当p中包含' * '时，当前位的值取决于该列前两位的值
s\p(true) a b c a F(此时的false为初始化时的值) F F *(match[0][2] = match[0][0]，往下如果有*则同理) T F F -
当前s中的字符与p中的字符匹配时，假设为match[ s -1 ][ p - 1 ]，这个时候整个s是否能与p匹配取决于match[ s - 2 ][ p - 2 ]的值
s\p(true) a b c a T T F b T T F c F F F 假设当前s字符为上方表格中的横向b，且p中字符也为竖列的b，那么此时，match数组的该值是否为true，取决于左上角a与a的匹配值。
题解代码如下：
class Solution {
private boolean isMatch(String s, String p) {
if (null == s || null == p) {
return false;
}
if ("*".equals(p)) {
return true;
}
int sLength = s.length();
int pLength = p.length();
boolean[][] match = new boolean[sLength + 1][pLength + 1];
match[0][0] = true;
for (int i = 1; i <= pLength; i++) {
if (p.charAt(i - 1) == '*') {
match[0][i] = match[0][i - 2];
}
}
for (int si = 1; si <= sLength; si++) {
for (int pi = 1; pi <= pLength; pi++) {
if (p.charAt(pi - 1) == '.' || p.charAt(pi - 1) == s.charAt(si - 1)) {
// 单个字符匹配
// 此时，若匹配串中的上一个字符和正则串的上一个字符是可以匹配的
// 那么到当前为止，整个匹配串和正则串都是匹配的
match[si][pi] = match[si - 1][pi - 1];
} else if (p.charAt(pi - 1) == '*') {
// 若当前正则串的该字符为*
if (p.charAt(pi - 2) == s.charAt(si - 1) || p.charAt(pi - 2) == '.') {
// 若此时匹配串中的该字符，与p中前一个字符可以匹配。
// 或者在该字符之前，s与p是匹配的，那么当前的字符也是可以匹配的
// 如，s=abcc，p=ab*
// 假设当前字符为s中的最后一位：c，且正则字符为*
// 那么在c之前，s如果与p是匹配的。则此时的c也是可以匹配的
match[si][pi] = match[si][pi - 2] || match[si - 1][pi];
} else {
match[si][pi] = match[si][pi - 2];
}
}
}
}
return match[sLength][pLength];
}
}