安徽弘泰建设管理有限公司网站,设计师培训多久,合肥企业网站制作公司,个人网站工商备案题目描述#xff1a;
给你一个输入字符串 (s) 和一个字符模式 (p) #xff0c;请你实现一个支持 ? 和 * 匹配规则的通配符匹配#xff1a; ? 可以匹配任何单个字符。 * 可以匹配任意字符序列#xff08;包括空字符序列#xff09;。 判定匹配成功的充要条件是#xff…题目描述
给你一个输入字符串 (s) 和一个字符模式 (p) 请你实现一个支持 ? 和 * 匹配规则的通配符匹配 ? 可以匹配任何单个字符。 * 可以匹配任意字符序列包括空字符序列。 判定匹配成功的充要条件是字符模式必须能够 完全匹配 输入字符串而不是部分匹配。 示例 1
输入s aa, p a 输出false 解释a 无法匹配 aa 整个字符串。 示例 2
输入s aa, p * 输出true 解释* 可以匹配任意字符串。 示例 3
输入s cb, p ?a 输出false 解释? 可以匹配 c, 但第二个 a 无法匹配 b。
提示
0 s.length, p.length 2000 s 仅由小写英文字母组成 p 仅由小写英文字母、? 或 * 组成 思路描述 对于大多数的字符串的题目我们都可以使用动态规划来解决。同样这个题目也可以使用动态规划。 因为存在两个字符串因此我们应该使用二维dp数组dp[i][j]表示当s字符串的长度为i时p字符串的长度为j时此时是否能够匹配上如果可以就是true否则就为false。 dp[i][j]的取值根据不同的情况要考虑不同的策略求出而其的取值必然与dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]的值有关可以认为是动态规划的一种套路。 当p字符串的第j号位置的字符为*时第一、需要考虑前j-1个位置的子串是否与s的第i元素为结尾的子串是否匹配。第二、需要考虑前j个位置的子串是否与s的第i-1元素为结尾的子串是否匹配。取两者的“或”关系。 当p字符串的第j号位置的字符为?或者p字符串的第j号位置的字符和s字符串的第i号位置的字符相同时直接就可以取dp[i-1][j-1]的值。
代码
class Solution {public boolean isMatch(String s, String p) {int m s.length();int n p.length();boolean[][] dp new boolean[m 1][n 1];dp[0][0] true;for (int i 1; i n; i) {if (p.charAt(i - 1) *) {dp[0][i] true;} else {break;}}for (int i 1; i m; i) {for (int j 1; j n; j) {if (p.charAt(j - 1) *) {dp[i][j] dp[i][j - 1] || dp[i - 1][j];} else if (p.charAt(j - 1) ? || s.charAt(i - 1) p.charAt(j - 1)) {dp[i][j] dp[i - 1][j - 1];}}}return dp[m][n];}
}
提交结果
