网站建设优化托管,小程序制作教学,万齐网站建设,wordpress主题mirana这道题我一看就有印象#xff0c;我室友算法课设抽到这题#xff0c;他当时有个bug让我帮他看一下#xff0c;然后我就大概看了一下他的算法#xff0c;他是用动态规划写的#xff0c;用了一个二维数组#xff0c;然后我就试着按照这个思路去写#xff0c;想了一会还是没… 这道题我一看就有印象我室友算法课设抽到这题他当时有个bug让我帮他看一下然后我就大概看了一下他的算法他是用动态规划写的用了一个二维数组然后我就试着按照这个思路去写想了一会还是没有思路就看题解了
class Solution {public boolean isMatch(String s, String p) {// .可以代替所有字符*前面的一个字符可以出现任意次包括0次int m s.length();int n p.length();boolean[][] dp new boolean[m1][n1];dp[0][0] true;for(int i 0; im; i){for(int j1;jn;j){if(p.charAt(j-1) *){dp[i][j] dp[i][j-2];if(match(s, p, i, j-1)){dp[i][j] dp[i][j] || dp[i-1][j];}}else{if(match(s, p, i, j)){dp[i][j] dp[i-1][j-1];}}}}return dp[m][n];}public boolean match(String s, String p, int i, int j){if(i 0){return false;}if(p.charAt(j-1) .){return true;}return s.charAt(i-1) p.charAt(j-1);}}
dp[i][i]表示s的前i个字符与p的前j个是否匹配进行状态转移时考虑p的第j个字符
1如果第j个字符是一个字母那么必须在s中匹配一个相同的小写字母。 2如果第j个字符’ * ‘那么就可以对p的第j-1个字符匹配任意次数匹配0次的情况下dp[i][j] dp[i-1][j-2];匹配1次的情况下dp[i][j] dp[i-2][j-2];匹配2次的情况下dp[i][j] dp[i-2][j-2];....... 所以综合两种情况有 matches是判断两个字符是否匹配的方法如果字符相同或者模板中的字符是 . 就返回true否则返回false。
dp[0][0] true,当两个字符是空字符时返回true最后返回dp[m][n],m是s的长度n是p的长度。
