題目
描述
給你一個(gè)字符串 s 和一個(gè)字符規(guī)律 p鹏氧，請你來實(shí)現(xiàn)一個(gè)支持 '.' 和 '*' 的正則表達(dá)式匹配炒瘟。
'.' 匹配任意單個(gè)字符
'*' 匹配零個(gè)或多個(gè)前面的那一個(gè)元素
所謂匹配黎比，是要涵蓋整個(gè)字符串s的礼预，而不是部分字符串眠砾。
說明:
-
s可能為空，且只包含從a-z的小寫字母托酸。 -
p可能為空褒颈，且只包含從a-z的小寫字母柒巫，以及字符.和*。
示例 1:
輸入:
s = "aa"
p = "a"
輸出: false
解釋: "a" 無法匹配 "aa" 整個(gè)字符串谷丸。
示例 2:
輸入:
s = "aa"
p = "a*"
輸出: true
解釋: 因?yàn)?'*' 代表可以匹配零個(gè)或多個(gè)前面的那一個(gè)元素, 在這里前面的元素就是 'a'堡掏。因此，字符串 "aa" 可被視為 'a' 重復(fù)了一次淤井。
示例 3:
輸入:
s = "ab"
p = ".*"
輸出: true
解釋: ".*" 表示可匹配零個(gè)或多個(gè)（'*'）任意字符（'.'）布疼。
示例 4:
輸入:
s = "aab"
p = "c*a*b"
輸出: true
解釋: 因?yàn)?'*' 表示零個(gè)或多個(gè)，這里 'c' 為 0 個(gè), 'a' 被重復(fù)一次币狠。因此可以匹配字符串 "aab"。
示例 5:
輸入:
s = "mississippi"
p = "mis*is*p*."
輸出: false
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/regular-expression-matching
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有砾层。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)漩绵，非商業(yè)轉(zhuǎn)載請注明出處。
解答
思路
使用動(dòng)態(tài)規(guī)劃的方法：
- 狀態(tài)矩陣：dp[i][j] 表示s的前i個(gè)字符是否可以被p的前j個(gè)字符匹配.
- 轉(zhuǎn)移方程：
2.1 如果p[j] == s[j]肛炮，那么dp[i][j] = dp[i-1][j-1]
2.2 如果p[j] == '.'止吐，那么dp[i][j] = dp[i-1][j-1]
2.3 如果p[j] == '*'：
2.3.1 如果p[j - 1] != s[i]，那么dp[i][j] = dp[i][j-2] // 也就是說*匹配了個(gè)寂寞侨糟，讓前面的字符無效了
2.3.2 如果p[j - 1] == s[i]或者p[j-1] == '.'：
- 要么dp[i][j] = dp[i-1][j] // * 匹配到了多個(gè)字符
- 要么dp[i][j] = dp[i][j-1] // * 匹配了一個(gè)字符
- 要么dp[i][j] = dp[i][j-2] // * 匹配了個(gè)寂寞
代碼
class Solution {
public boolean isMatch(String s, String p) {
if (s == null || p == null) {
return false;
}
int m = s.length(), n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
// ""和匹配關(guān)系的初始化
// 奇數(shù)位不管什么字符都是false碍扔，偶數(shù)位為*時(shí)，dp[0][i] = dp[0][i-2]
for (int i = 2; i <= n; i += 2) {
if (p.charAt(i - 1) == '*') {
dp[0][i] = dp[0][i - 2];
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
char sc = s.charAt(i - 1);
char pc = p.charAt(j - 1);
if (sc == pc || pc == '.') {
dp[i][j] = dp[i - 1][j - 1];
} else if (pc == '*') {
if (dp[i][j - 2]) {
dp[i][j] = true;
} else if (sc == p.charAt(j - 2) || p.charAt(j - 2) == '.') {
dp[i][j] = dp[i - 1][j];
}
}
}
}
return dp[m][n];
}
}
