題目描述
給定一個(gè)字符串 (s) 和一個(gè)字符模式 (p) ，實(shí)現(xiàn)一個(gè)支持 '?' 和 '*' 的通配符匹配。
'?' 可以匹配任何單個(gè)字符。 '*' 可以匹配任意字符串（包括空字符串）。 兩個(gè)字符串完全匹配才算匹配成功。
示例
題目鏈接
動(dòng)態(tài)規(guī)劃
可以使用dp[i][j]來(lái)保存s的前i個(gè)字符與p的前j個(gè)字符匹配情況。當(dāng)p取到‘?’或者兩個(gè)字符串取出來(lái)的字符相同時(shí)。只需要看dp[i-1][j-1]的情況即可，也就是之前的字符串匹配情況。if(p[j]==s[i] || p[j]=='?') dp[i][j]=dp[i-1][j-1]
若p取出來(lái)的是‘’時(shí)，我們需要考慮兩種情況，匹配一個(gè)空串時(shí)，則當(dāng)s的前i個(gè)字符與p的前j-1個(gè)字符匹配成功則認(rèn)為匹配成功。另一種情況則是*匹配s[i]，此時(shí)若s的前i-1個(gè)字符與p的前j個(gè)字符匹配成功則認(rèn)為匹配成功。即if(p[j]=='*')dp[i][j]=dp[i-1][j] || dp[i][j-1].
注意，當(dāng)*匹配是s[i]時(shí)，dp[i][j]=dp[i-1][j]而不是dp[i-1][j-1]因?yàn)槠ヅ湟粋€(gè)字符后，*仍然可以繼續(xù)匹配其他字符或空串，若寫成dp[i][j]=dp[i-1][j-1]則意味著拋棄了這個(gè)*,它不繼續(xù)匹配。如s="abc" ，p="a*" *匹配c后我們查看“ab”與“a*”的匹配情況，而不是跳過(guò)*直接查看“ab”與"a"的匹配情況。
我們還需要注意邊界情況，空串與空串是可以匹配成功的，所以dp[0][0]=true.若p取空串，則dp[i][0]=false(i>0).若s為空則只有當(dāng)p[0:j]為'*'時(shí)dp[0][j]=ture 否則為false。
//dp[i][j]保存s的前i個(gè)字符與p的前j個(gè)字符匹配情況。
boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
dp[0][0] = true;
for (int i = 0; i < p.length(); i++) {//當(dāng)p的前i個(gè)字符均為*時(shí)，才能匹配s為空的情況
if (p.charAt(i) == '*')
dp[0][i + 1] = true;
else break;
}
for (int i = 1; i <= s.length(); i++) {
for (int j = 1; j <= p.length(); j++) {
if (p.charAt(j - 1) == '*') {//*匹配空串或s的一個(gè)字符
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
} else if (p.charAt(j - 1) == '?' || p.charAt(j - 1) == s.charAt(i - 1)) {//單個(gè)字符匹配
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[s.length()][p.length()];
動(dòng)態(tài)規(guī)劃可以通過(guò)測(cè)試，但效率并不算高。
據(jù)說(shuō)這題用貪心算法的效率會(huì)比動(dòng)態(tài)規(guī)劃高，有時(shí)間研究一下
