哪些网站专门做康复科,网站开发中如何制作登录页面,珠海模板开发建站,上饶哪里可以学网站建设提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 目录
一、问题描述
二、常规算法
三、动态规划算法
总结 提示#xff1a;以下是本篇文章正文内容#xff0c;下面案例可供参考
一、问题描述
给定一个字符串 (s) 和一… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 目录
一、问题描述
二、常规算法
三、动态规划算法
总结 提示以下是本篇文章正文内容下面案例可供参考
一、问题描述
给定一个字符串 (s) 和一个字符模式 (p) 实现一个支持 ? 和 * 的通配符匹配
? 可以匹配任何单个字符。 * 可以匹配任意字符串包括空字符串。
两个字符串完全匹配才算匹配成功。
s 可能为空且只包含从 a-z 的小写字母。 p 可能为空且只包含从 a-z 的小写字母以及字符 ? 和 *。
输入: s aa p a 输出: false 解释: a 无法匹配 aa 整个字符串。
输入: s aa p * 输出: true 解释: * 可以匹配任意字符串。
输入: s cb p ?a 输出: false 解释: ? 可以匹配 c, 但第二个 a 无法匹配 b。
输入: s adceb p *a*b 输出: true 解释: 第一个 * 可以匹配空字符串, 第二个 * 可以匹配字符串 dce。
输入: s acdcb p a*c?b 输出: false
二、常规算法
解题思路
我们将这个题拆解一下分为不包含*的场景和包含*的场景
1、不包含*的场景我们逐位进行比对即可得出最终的结论
2、包含*的场景我们无法确定起点位置所以我们用s的每一个字符去和p的每一个字符进行匹配记录匹配的结果最终相当于成了一道寻路题了只不过限制了前进方向为向下或者向右起点从首个字符能匹配到的地方开始算起。
代码示例
public void test() {String s acdcb;String p a*c?b;// 模式匹配串中不包含*if (!p.contains(*)) {if (s.length() ! p.length()) {System.out.println(false);return;}for (int i 0; i s.length(); i) {if (p.charAt(i) ? || s.charAt(i) p.charAt(i)) {continue;}System.out.println(false);return;}System.out.println(false);return;}// 模式匹配串中包含*, 我们用s中的每一个字符都去和p中的每个字符匹配, 结果保存在一个二维数组中, s中有几个字符, 就有几行数据int[][] array new int[s.length()][p.length()];for (int i 0; i s.length(); i) {for (int j 0; j p.length(); j) {if (p.charAt(j) ? || p.charAt(j) * || s.charAt(i) p.charAt(j)) {// 单个字符匹配, 标记为1array[i][j] 1;continue;}// 单个字符不匹配, 标记为0array[i][j] 0;}}// 最后我们得到一个全部标记了0或1的二维数组, 起点是第一行中的某个元素, 要求从这个元素开始向下或者向右移动, 最终能抵达斜对角的位置for (int j 0; j p.length(); j) {if (array[0][j] 1) {boolean can canReach(array, 0, j);if (!can) {continue;}System.out.println(true);return;}}
}public boolean canReach(int[][] array, int row, int col) {// 如果当前位置已经到达右下角对角线返回trueif (row array.length - 1 col array[0].length - 1) {return true;}// 如果当前位置超出矩阵范围或者元素为0返回falseif (row array.length || col array[0].length || array[row][col] 0) {return false;}// 递归向下或向右移动return canReach(array, row 1, col) || canReach(array, row, col 1);
}
常规算法胜于更易理解将复杂问题拆解为简单的子问题逐个破解。
三、动态规划算法
解题思路
最终的匹配结果依赖于最后一个字符的匹配结果最后一个字符的匹配结果又依赖于前一个字符的匹配结果依此类推直至首个字符匹配成功。那么前一个字符的匹配结果在该字符的匹配结果的什么位置呢答案是上方或者左侧。由于p中包含*字符这个*可能代表0 ~ N个字符所以可能是跳过该位置有可能是跨了多个位置。我们约定横跨是向右跳过是向下。
所以当出现p中某位是*时它取的结果来自它的上方和左侧如果有一个是通过本位置即为通过。
代码示例
public void test() {String s aa;String p a;// 初始化动态规划数组boolean[][] dp new boolean[s.length() 1][p.length() 1];// 当模式串为空时只有当字符串也为空时才匹配成功dp[0][0] true;// 处理模式串中的第一个字符for (int j 1; j p.length(); j) {if (p.charAt(j - 1) *) {dp[0][j] dp[0][j - 1];}}// 动态规划过程for (int i 1; i s.length(); i) {for (int j 1; j p.length(); j) {if (p.charAt(j - 1) ? || s.charAt(i - 1) p.charAt(j - 1)) {dp[i][j] dp[i - 1][j - 1];} else if (p.charAt(j - 1) *) {dp[i][j] dp[i - 1][j] || dp[i][j - 1];}}}System.out.println(JSON.toJSONString(dp));// 返回最终匹配结果System.out.println(dp[s.length()][p.length()]);
} 动态规划算法要找一下规律代码比较简洁。 总结
解题过程已奉上快快练起来简单到有手就行
