44. Wildcard Matching 发表于 2022-05-16 1234567891011121314151617181920212223242526272829303132333435363738394041class Solution { public boolean isMatch(String s, String p) { // 定义 dp[i][j] 表示 s 字符串前 i 个字符与 p 字符串前 j 个字符是否匹配 boolean[][] dp = new boolean[s.length() + 1][p.length() + 1]; dp[0][0] = true; // 空字符串与空模式匹配 // 空模式与非空字符串不匹配 for (int i = 1; i < dp.length; i++) { dp[i][0] = false; } // 非空模式需要单独计算 for (int i = 0; i <= s.length(); i++) { for (int j = 1; j <= p.length(); j++) { char c = p.charAt(j - 1); // 注意索引为 i - 1 if (c == '*') { if (j - 1 >= 0) { // 如果 * 匹配空字符串 dp[i][j] |= dp[i][j - 1]; } // 如果 * 匹配任意字符串,那么肯定由 dp[i - 1][j] 转移而来 if (i - 1 >= 0) { dp[i][j] |= dp[i - 1][j]; } } else if (c == '?') { if (i - 1 >= 0) { dp[i][j] |= dp[i - 1][j - 1]; } } else { // c is alpha if (i - 1 >= 0 && s.charAt(i - 1) == c) { dp[i][j] |= dp[i - 1][j - 1]; } } } } return dp[s.length()][p.length()]; }} Reference44. Wildcard Matching