Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Note:
-
scould be empty and contains only lowercase lettersa-z. -
pcould be empty and contains only lowercase lettersa-z, and characters like.or*.
PS : 默认pattern是符合正则式规则的。
第一次看到这个题的时候一点思路都没。直接看解答了，学习了一下动态规划（Dynamic Programming）
class Solution {
public boolean isMatch(String s, String p) {
int sLen = s.length();
int pLen = p.length();
boolean[][] dp = new boolean[sLen + 1][pLen + 1];
dp[0][0] = true;//当s为空以及p为空时，匹配。
for (int i = 0;i <= sLen;i++){//当s为空时，p == ".*" 等可以匹配，故从长度0开始。
for (int j = 1; j <= pLen; j++) {//当p为空s不为空时，一定不匹配，bool数组初始化时已赋值为false，故从长度1开始。
if (p.charAt(j - 1) == '*'){
dp[i][j] = dp[i][j-2] //匹配零次前个字符
|| (i > 0
&& dp[i-1][j]//匹配第n次时的前提是，至少匹配n-1次时已成功
&& (p.charAt(j - 2) == '.' || s.charAt(i - 1) == p.charAt(j - 2))); //匹配一次前个字符
}else {
dp[i][j] = i > 0 //字符串为空时一定不匹配
&& dp[i - 1][j - 1] //多匹配一个字符的前提是前面的字符已匹配成功
&& (p.charAt(j - 1) == '.' || s.charAt(i - 1) == p.charAt(j - 1));//如果Pattern值为'.'时匹配所有，或者两个字符相等
}
}
}
return dp[sLen][pLen];
}
}
稍微优化了一下空间占用：
class Solution {
public boolean isMatch(String s, String p) {
int sLen = s.length();
int pLen = p.length();
boolean[][] dp = new boolean[2][pLen + 1];
dp[0][0] = true;
for (int i = 0; i <= sLen; i++){
if (i == 2){
dp[i % 2][0] = false;
}
for (int j = 1; j <= pLen; j++) {
if (p.charAt(j - 1) == '*'){
dp[i % 2][j] = dp[i % 2][j - 2]
|| (i > 0
&& dp[(i - 1) % 2][j]
&& (p.charAt(j - 2) == '.' || s.charAt(i - 1) == p.charAt(j - 2)));
}else {
dp[i % 2][j] = i > 0
&& dp[(i - 1) % 2][j - 1]
&& (p.charAt(j - 1) == '.' || s.charAt(i - 1) == p.charAt(j - 1));
}
}
}
return dp[sLen % 2][pLen];
}
}
