<分区>
我遇到了以下实现(https://discuss.leetcode.com/topic/40371/easy-dp-java-solution-with-detailed-explanation),但并没有完全理解它是如何工作的——评论了我是如何迷路的:
boolean isMatch(String s, String p) {
if(s==null || p==null) {
return false;
}
// Why add an additional length to the string lengths?
boolean[][] dp = new boolean[s.length()+1][p.length()+1];
dp[0][0] = true;
// What’s the reason for this check? If p were to have ‘*’ at i=3, it would simply pass
for(int i=0; i<p.length(); i++) {
if(p.charAt(i)=='*' && dp[0][i-1]) {
dp[0][i+1] = true;
}
}
for(int i=0; i<s.length(); i++) {
for(int j=0; j<p.length(); j++) {
// Shouldn’t dp[i][j] just equal to true? Why set a boolean value to characters ahead?
if(p.charAt(j)=='.') {
dp[i+1][j+1] = dp[i][j];
}
// Same question as prior
if(p.charAt(j)==s.charAt(i)) {
dp[i+1][j+1] = dp[i][j];
}
if(p.charAt(j)=='*') {
// Not quiet understanding what the following checks are for and how they work
if(p.charAt(j-1)!=s.charAt(i) && p.charAt(j-1)!='.') {
dp[i+1][j+1] = dp[i+1][j-1];
} else {
dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
}
}
}
}
return true;
}
预先感谢您,一定会投票赞成/接受答案