import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * @param str string字符串 * @param pattern string字符串 * @return bool布尔型 */ //动态规划的解法 public boolean match (String str, String pattern) { if(pattern.length() == 0) { return str.length() == 0 ; } char[] strA = str.toCharArray() ; char[] patternA = pattern.toCharArray() ; //dp[i][j]表示str前i个字符和pattern前j个字符是否匹配 boolean dp[][] = new boolean[str.length() + 1][pattern.length() + 1] ; dp[0][0] = true ; for(int i = 0 ; i <= str.length() ; i ++) { for(int j = 0 ; j <= pattern.length() ; j ++) { //如果当前模式串字符是不是 * if(j > 0 && patternA[j-1] != '*') { //直接匹配,匹配上就转移 if(i > 0 && j > 0 && matcher(strA[i-1] , patternA[j-1])) { dp[i][j] = dp[i-1][j-1] ; } } else { if(j >= 2) { //看 *前面的p[j-2]是否和s[i]匹配,若匹配则可以选择将p[j-2]*直接略过,也可以继续匹配 if(i > 0 && matcher(strA[i-1] , patternA[j-2])) { dp[i][j] = dp[i-1][j] || dp[i][j-2] ; } else { //只能将p[i-2]直接略过 dp[i][j] = dp[i][j-2] ; } } } } } return dp[strA.length][patternA.length] ; } public boolean matcher(char i , char j) { if(i == j || j == '.') { return true ; } return false ; } }