LeetCode 10
題目
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).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
思想
這道題應(yīng)該是LeetCode題庫(kù)中Hard題比較簡(jiǎn)單的一道了，就是一個(gè)很常規(guī)的DP題。（我居然還去試了一下貪心~）
既然比較簡(jiǎn)單就不廢話了，直接說動(dòng)態(tài)轉(zhuǎn)移方程組了坏逢，我們首先定義一些變量方便解釋贝咙，被匹配串為s崎页，模式串為p孝宗。狀態(tài)轉(zhuǎn)移數(shù)組f[i][j]表示利用p的前j個(gè)字符匹配s的前i個(gè)字符的匹配結(jié)果（成功為true捣卤，失敗為false）异逐。
那么狀態(tài)轉(zhuǎn)移方程就很簡(jiǎn)單了：
- s[i] == p[j] || p[j] == '.'捶索，那么f[i][j] = f[i-1][j-1]，也就是既然s串的第i個(gè)字符能和p串的第j個(gè)字符匹配灰瞻，那么如果s串的前i-1個(gè)字符和p串的前j-1個(gè)字符能匹配則s串的前i個(gè)和p串的前j個(gè)則能匹配腥例，反之不能。
-
p[j] == '*'：
- s[i] != p[j-1] && p[j-1] != '.'箩祥，那么f[i][j] = f[i][j-2]院崇，也就是*號(hào)前面的那個(gè)字符在匹配的過程當(dāng)中一個(gè)都不使用。
- else袍祖，那么f[i][j] = f[i-1][j] || f[i][j-1] || f[i][j-2]底瓣，也就是說要么使用'*'號(hào)進(jìn)行匹配(f[i-1][j])，要么只使用'*'號(hào)前面的那個(gè)字符匹配蕉陋，不使用'*'匹配(f[i][j-1])捐凭，要么'*'號(hào)前面的那個(gè)字符在匹配的過程當(dāng)中一個(gè)都不使用（f[i][j-2]），只要有一個(gè)是true則能夠匹配凳鬓。
既然是DP題茁肠，那么邊界條件是必須考慮的部分。因?yàn)槲乙婚_始i是從1到s.length()缩举，j是1到p.length()垦梆。首先一來就能想到f[0][0]是true，其他都是false仅孩。但是這個(gè)邊界條件是不夠的托猩。比如isMatch("aab", "c*a*b")，f[1][3]應(yīng)該是從f[0][2]轉(zhuǎn)移過來的辽慕，所以需要更多的邊界條件京腥，也就是一開始的*是能匹配空字符串的。所以我把i改到了從0開始,并且第二條也添加了i=0溅蛉，f[i][j] = f[i][j-2]公浪。
代碼
public boolean isMatch(String s, String p) {
boolean[][] f = new boolean[s.length() + 1][p.length() + 1];
for (int i = 0; i <= s.length(); i++) {
for (int j = 0; j <= p.length(); j++) {
f[i][j] = false;
}
}
f[0][0] = true;
for (int i = 0; i <= s.length(); i++) {
for (int j = 1; j <= p.length(); j++) {
if (i > 0 && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.')) {
f[i][j] = f[i - 1][j - 1];
}
if (p.charAt(j - 1) == '*') {
if (i == 0 || (s.charAt(i - 1) != p.charAt(j - 2) && p.charAt(j - 2) != '.')) {
f[i][j] = f[i][j - 2];
} else {
f[i][j] = f[i - 1][j] || f[i][j - 1] || f[i][j - 2];
}
}
}
}
return f[s.length()][p.length()];
}
