自己做网站要学什么软件,专业小程序制作开发平台,网站建设成品,漫画网站建设题目出处
44-通配符匹配-题目出处
题目描述 个人解法 思路#xff1a; todo代码示例#xff1a;#xff08;Java#xff09; todo复杂度分析 todo官方解法
44-通配符匹配-官方解法
前言
本题与10. 正则表达式匹配非常类似#xff0c;但相比较而言#xff0c;本题稍…题目出处
44-通配符匹配-题目出处
题目描述 个人解法 思路 todo代码示例Java todo复杂度分析 todo官方解法
44-通配符匹配-官方解法
前言
本题与10. 正则表达式匹配非常类似但相比较而言本题稍微容易一些。因为在本题中模式 p 中的任意一个字符都是独立的即不会和前后的字符互相关联形成一个新的匹配模式。因此本题的状态转移方程需要考虑的情况会少一些。
方法1动态规划 思路 代码示例Java public class Solution1 {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];}}复杂度分析 时间复杂度O(mn)其中 m 和 n 分别是字符串 s 和模式 p 的长度。空间复杂度O(mn)即为存储所有 (m1)(n1) 个状态需要的空间。此外在状态转移方程中由于 dp[i][j] 只会从 dp[i][…] 以及 dp[i−1][…] 转移而来因此我们可以使用滚动数组对空间进行优化即用两个长度为 n1 的一维数组代替整个二维数组进行状态转移空间复杂度为 O(n)。
方法2:贪心算法 思路 // 我们用 sIndex 和 pIndex 表示当前遍历到 s 和 p 的位置
// 此时我们正在 s 中寻找某个 u_i
// 其在 s 和 p 中的起始位置为 sRecord 和 pRecord// sIndex 和 sRecord 的初始值为 0
// 即我们从字符串 s 的首位开始匹配
sIndex sRecord 0// pIndex 和 pRecord 的初始值为 1
// 这是因为模式 p 的首位是星号那么 u_1 的起始位置为 1
pIndex pRecord 1while sIndex s.length and pIndex p.length doif p[pIndex] * then// 如果遇到星号说明找到了 u_i开始寻找 u_i1pIndex 1// 记录下起始位置sRecord sIndexpRecord pIndexelse if match(s[sIndex], p[pIndex]) then// 如果两个字符可以匹配就继续寻找 u_i 的下一个字符sIndex 1pIndex 1else if sRecord 1 s.length then// 如果两个字符不匹配那么需要重新寻找 u_i// 枚举下一个 s 中的起始位置sRecord 1sIndex sRecordpIndex pRecordelse// 如果不匹配并且下一个起始位置不存在那么匹配失败return Falseend if
end while// 由于 p 的最后一个字符是星号那么 s 未匹配完那么没有关系
// 但如果 p 没有匹配完那么 p 剩余的字符必须都是星号
return all(p[pIndex] ~ p[p.length - 1] *) 代码示例Java public class Solution2 {public boolean isMatch(String s, String p) {int sRight s.length(), pRight p.length();while (sRight 0 pRight 0 p.charAt(pRight - 1) ! *) {if (charMatch(s.charAt(sRight - 1), p.charAt(pRight - 1))) {--sRight;--pRight;} else {return false;}}if (pRight 0) {return sRight 0;}int sIndex 0, pIndex 0;int sRecord -1, pRecord -1;while (sIndex sRight pIndex pRight) {if (p.charAt(pIndex) *) {pIndex;sRecord sIndex;pRecord pIndex;} else if (charMatch(s.charAt(sIndex), p.charAt(pIndex))) {sIndex;pIndex;} else if (sRecord ! -1 sRecord 1 sRight) {sRecord;sIndex sRecord;pIndex pRecord;} else {return false;}}return allStars(p, pIndex, pRight);}public boolean allStars(String str, int left, int right) {for (int i left; i right; i) {if (str.charAt(i) ! *) {return false;}}return true;}public boolean charMatch(char u, char v) {return u v || v ?;}}复杂度分析 On the Average-case Complexity of Pattern Matching with Wildcards 【来自于Cornell University康奈尔大学】
结语 AC自动机 Set Matching and Aho-Corasick Algorithm【来自于Carnegie Mellon University卡内基梅隆大学 ,Java之父詹姆斯·高斯林 James Gosling在该校获得计算机科学博士学位】
考察知识点
1.通配符匹配
收获
1.通配符 2.伪代码
Gitee源码位置
44-通配符匹配-源码
