-
LeetCode高频题44. 通配符匹配
LeetCode高频题44. 通配符匹配
提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题
题目
给定一个字符串 (s) 和一个字符模式 § ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。
‘?’ 可以匹配任何单个字符。
‘*’ 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/wildcard-matching
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一、审题
示例 1:
输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。
示例 2:输入:
s = “aa”
p = ""
输出: true
解释: '’ 可以匹配任意字符串。
示例 3:输入:
s = “cb”
p = “?a”
输出: false
解释: ‘?’ 可以匹配 ‘c’, 但第二个 ‘a’ 无法匹配 ‘b’。
示例 4:输入:
s = “adceb”
p = “ab”
输出: true
解释: 第一个 ‘’ 可以匹配空字符串, 第二个 '’ 可以匹配字符串 “dce”.
示例 5:输入:
s = “acdcb”
p = “a*c?b”
输出: false
二、解题
本题跟之间讲过的这个题，基本一模一样，微微有点区别，挺难
本题，最后能优化到这个地步：
关键在于你如何暴力尝试，解决这个问题，然后才能改动态规划方法！！基础知识:
【1】LeetCode高频题10：正则表达式匹配那个题目，它是.和星
.跟本题的？一样，都是匹配任意字符
当时的星‘*’ ，可以匹配零个或多个前面的那一个元素【本题不是哦】本题的星’*’ 可以匹配**任意字符串（**包括空字符串）。
看懂这个区别就好办了
为s能通过p变出来吗？？本题没有之前的题难，之前那个题，难上天了
暴力尝试类似的
f(s,p,si, pi)
s的si–N-1范围，能否被p的pi–M-1范围匹配出来
主函数调用：
f(s,p,si=0, pi=0)f(s,p,si, pi)具体咋写呢？？
看边界条件（1）base case：当si==N，越界了
s的si–N-1就是空串“”
什么情况下能被p从pi–M-1范围匹配出来
首先pi=M，p的pi–M-1就是空串“”，肯定可以配出来的，此刻s=p
其次，pi=后面一串，需要想办法变空，才能变成空串“”，匹配s的si–N-1，
所以必须得让pi=星才行，这样才能让星变出来“”空串，而且，
与此同时，保证pi+1–M位置也必须能匹配，同时满足上面的条件，才能OK
比如：
代码这么撸：
后续的情况：
（2）si就没到结尾，还有东西，你瞅瞅pi=M吗？
如果pi=M，那不好意思，p的pi–M-1就是空串啊“”，不可能生出s的si–N-1的，返回false（3）si没到结尾，且pi也没有到结尾，有戏了
那就要看pi能不能匹配出si了
如果此时si与pi压根没法匹配，而且pi既不是？也不是星，那不好意思，不行的
下面的胡啊，pi可能是与si相同，或者时？或者时星（4）可能pi字符就是si字符，同时保证p的pi+1–M-1匹配出s的si+1–N-1即可
可能pi是？，可以变si，同时保证p的pi+1–M-1匹配出s的si+1–N-1即可
比如：
（5）pi既不是si，也不是？而是星
那就要看pi能不能匹配出si，或者si–某一段了
比如：
下面的星，可以变一个a，或者ab，或者abc等等等等，且保证s后续和pi后续都能匹配，那就OK
即枚举每一个子串s的si–i范围内，pi处的星变si–i范围上之后，后续能匹配吗？
有其一即可手撕代码OK的
public boolean isMatch(String s, String p) { if (s.equals("") && p.equals("")) return true; if (p.equals("")) return false; //如果s空，但是p是一堆星，是可以哦，过滤别错了 char[] str = s.toCharArray(); char[] ptr = p.toCharArray(); return f(str, ptr, 0, 0);//s整个范围到p的整个范围能匹配吗？ } //f(s,p,si, pi) //s的si--N-1范围，能否被p的pi--M-1范围匹配出来 public static boolean f(char[] str, char[] ptr, int si, int pi){ //1）base case：当si==N，越界了 //s的si--N-1就是空串“” //什么情况下能被p从pi--M-1范围匹配出来 //首先pi=M，p的pi--M-1就是空串“”，肯定可以配出来的，此刻s=p //其次，pi=后面一串，需要想办法变空，才能变成空串“”，匹配s的si--N-1， //所以必须得让pi=星才行，这样才能让星变出来“”空串，而且， //与此同时，保证pi+1--M位置也必须能匹配，同时满足上面的条件，才能OK if(si == str.length){ if (pi == ptr.length) return true; return ptr[pi] == '*' && f(str, ptr, si, pi + 1);//后续也得配出空串 } //（2）si就没到结尾，还有东西，你瞅瞅pi=M吗？ //如果pi=M，那不好意思，p的pi--M-1就是空串啊“”，不可能生出s的si--N-1的，返回false if (pi == ptr.length) return false; //（3）si没到结尾，且pi也没有到结尾，有戏了 //那就要看pi能不能匹配出si了 //如果此时si与pi压根没法匹配，那不好意思，不行的 if (str[si] != ptr[pi] && ptr[pi] != '?' && ptr[pi] != '*') return false; //（4）可能pi字符就是si字符，同时保证p的pi+1--M-1匹配出s的si+1--N-1即可 //可能pi是？，可以变si，同时保证p的pi+1--M-1匹配出s的si+1--N-1即可 if (str[si] == ptr[pi] || ptr[pi] == '?') return f(str, ptr, si + 1, pi + 1); //pi既不是si，也不是？而是星 //那就要看pi能不能匹配出si，或者si--某一段了 //此刻pi已经是*了 //可以让*先变空试试： if(f(str, ptr, si, pi + 1)) return true;//这种也可以 for (int i = si; i < str.length; i++) { //枚举每一个子串，pi处的星变si--i范围上之后，后续能匹配吗？ if (f(str, ptr, i + 1, pi + 1)) return true;//有一个能匹配就算OK } //上面所有办法试了不行 return false; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
但是测试你发现时间超过限制了
但是能过一大部分，思路okok，只不过方法太暴力！当然的，暴力嘛！！
笔试AC解：从暴力递归改记忆化搜索代码，搞一个dp数组存si和pi处的状况，int数组，-1没填，0就是false，1就是true
dp数组
si取0–N，N+1长度，pi也会是M+1长度，取0–M
dp[si][pi]代表f暴力递归的含义：s的si–N-1返回上能由p的pi–M-1范围上匹配出来吗？能就填1，不能填0最开始都是-1，代表没有填
//超过时间限制了 //改DP，记忆化搜搜先试试 public boolean isMatchDP(String s, String p) { if (s.equals("") && p.equals("")) return true; if (p.equals("")) return false; //如果s空，但是p是一堆星，是可以哦，过滤别错了 char[] str = s.toCharArray(); char[] ptr = p.toCharArray(); //si取0--N，N+1长度，pi也会是 int N = str.length; int M = ptr.length; int[][] dp = new int[N + 1][M + 1];//由于false算是一个结果，放int for (int i = 0; i < N + 1; i++) { for (int j = 0; j < M + 1; j++) { dp[i][j] = -1; } } return f2(str, ptr, 0, 0, dp);//s整个范围到p的整个范围能匹配吗？ } //f(s,p,si, pi) //s的si--N-1范围，能否被p的pi--M-1范围匹配出来 public static boolean f2(char[] str, char[] ptr, int si, int pi, int[][] dp){ if (dp[si][pi] != -1) return dp[si][pi] == 1 ? true : false;//填过了 //1）base case：当si==N，越界了 //s的si--N-1就是空串“” //什么情况下能被p从pi--M-1范围匹配出来 //首先pi=M，p的pi--M-1就是空串“”，肯定可以配出来的，此刻s=p //其次，pi=后面一串，需要想办法变空，才能变成空串“”，匹配s的si--N-1， //所以必须得让pi=星才行，这样才能让星变出来“”空串，而且， //与此同时，保证pi+1--M位置也必须能匹配，同时满足上面的条件，才能OK if(si == str.length){ if (pi == ptr.length) { dp[si][pi] = 1; return true; } boolean ans = (ptr[pi] == '*' && f2(str, ptr, si, pi + 1, dp));//后续也得配出空串 dp[si][pi] = ans ? 1 : 0; return ans; } //（2）si就没到结尾，还有东西，你瞅瞅pi=M吗？ //如果pi=M，那不好意思，p的pi--M-1就是空串啊“”，不可能生出s的si--N-1的，返回false if (pi == ptr.length) { dp[si][pi] = 0; return false; } //（3）si没到结尾，且pi也没有到结尾，有戏了 //那就要看pi能不能匹配出si了 //如果此时si与pi压根没法匹配，那不好意思，不行的 if (str[si] != ptr[pi] && ptr[pi] != '?' && ptr[pi] != '*') { dp[si][pi] = 0; return false; } //（4）可能pi字符就是si字符，同时保证p的pi+1--M-1匹配出s的si+1--N-1即可 //可能pi是？，可以变si，同时保证p的pi+1--M-1匹配出s的si+1--N-1即可 if (str[si] == ptr[pi] || ptr[pi] == '?') { boolean ans = f2(str, ptr, si + 1, pi + 1, dp); dp[si][pi] = ans ? 1 : 0; return ans; } //pi既不是si，也不是？而是星 //那就要看pi能不能匹配出si，或者si--某一段了 //此刻pi已经是*了 //可以让*先变空试试： if(f2(str, ptr, si, pi + 1, dp)) { dp[si][pi] = 1; return true;//这种也可以 } for (int i = si; i < str.length; i++) { //枚举每一个子串，pi处的星变si--i范围上之后，后续能匹配吗？ if (f2(str, ptr, i + 1, pi + 1, dp)) { dp[si][pi] = 1; return true;//有一个能匹配就算OK } } //上面所有办法试了不行 dp[si][pi] = 0; return false; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
过程没问题
这次终于通过了public static void test(){ String s = "adceb"; String p = "*a*b"; Solution solution = new Solution(); System.out.println(solution.isMatch(s, p)); System.out.println(solution.isMatchDP(s, p)); s = "aa"; p = "*aa*b"; System.out.println(solution.isMatch(s, p)); System.out.println(solution.isMatchDP(s, p)); s = "aa"; p = "*"; System.out.println(solution.isMatch(s, p)); System.out.println(solution.isMatchDP(s, p)); s = "cb"; p = "?b"; System.out.println(solution.isMatch(s, p)); System.out.println(solution.isMatchDP(s, p)); s = "acdcb"; p = "a*c?b"; System.out.println(solution.isMatch(s, p)); System.out.println(solution.isMatchDP(s, p)); s = ""; p = "*****"; System.out.println(solution.isMatch(s, p)); System.out.println(solution.isMatchDP(s, p)); } public static void main(String[] args) { test(); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
true true false false true true true true false false true true- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
LeetCode测试
显然，还需要优化代码，这只是AC而已，还需要优化加速
里面有枚举行为，自然要把枚举行为优化掉！！！
笔试AC解：暴力递归改动态规划，根据f填写dp表，中间填好转移方程，最后返回dp[0][0]
记住啊，动态规划一点不是问题，不难
只要暴力递归f出来了，改动态规划就是玩
f中就si和pi俩变量，一个变量做行，一个变量做列的样本位置对应模型
上面记忆化搜索说过了
dp是一个表，代表：
si取0–N，N+1长度，pi也会是M+1长度，取0–M
dp[si][pi]代表f暴力递归的含义：s的si–N-1返回上能由p的pi–M-1范围上匹配出来吗？能就填1，不能填0
这里不在是10，我们直接填true或者false
返回五角星按个格子的值根据f的base case，就可以填最后一行，最后一列
你就知道
dp[N][M]=true
剩下的位置依赖pi+1
从pi=M-1开始填，从右往左填M行同时M列也可以填好
dp[N][M] = true; for (int pi = M - 1; pi >= 0; pi--) { dp[N][pi] = ptr[pi] == '*' && dp[M][pi + 1];//后续也得配出空串 }- 1
- 2
- 3
- 4
其余的dp[si][pi]怎么填嗯？？
f依赖谁呢，for循环那个发现是依赖si+1,pi+1，或者si的其他位置啥的
下面这样
所以咱们从下往上填，从右往左填dp这里要注意，我们枚举pi的星匹配si–后续一段长时，可以换一下
把si–si+i长度范围内拿去匹配pi的星
这样就换了一下：//剩下的默认dpij就是false for (int si = N - 1; si >= 0; si--) { for (int pi = M - 1; pi >= 0; pi--) { //暴力递归怎么写，就怎么改 //（3）si没到结尾，且pi也没有到结尾，有戏了 //那就要看pi能不能匹配出si了 //如果此时si与pi压根没法匹配，那不好意思，不行的 if (str[si] != ptr[pi] && ptr[pi] != '?' && ptr[pi] != '*') { dp[si][pi] = false; //要return的地方，continue continue; } //（4）可能pi字符就是si字符，同时保证p的pi+1--M-1匹配出s的si+1--N-1即可 //可能pi是？，可以变si，同时保证p的pi+1--M-1匹配出s的si+1--N-1即可 if (str[si] == ptr[pi] || ptr[pi] == '?') { dp[si][pi] = dp[si + 1][pi + 1]; continue; } //pi既不是si，也不是？而是星 //那就要看pi能不能匹配出si，或者si--某一段了 //此刻pi已经是*了 //可以让*先变空试试：跟下面i=0长度融合，空串 //该怎么枚举怎么枚举 for (int i = 0; i < N - si; i++) {//最大能匹配si--N，N-si长度 //这里要改改，不要弄si了，应该是星替换s多长的字符，剩下的继续陪 //枚举每一个子串，pi处的星变si--si+i范围上之后，后续能匹配吗？ if (dp[si + i][pi + 1]) { dp[si][pi] = true;//有一个能匹配就算OK //然后不要了 break; } } //上面所有办法试了不行，默认就是了return false; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
外面宏观调度填si和pi位置，内部根据f怎么填，咱就怎么填，但是融合f中for循环那的所有情况
枚举长度i=0–N-si这些状况
让pi的星去变空，1个si，2个si，3个si等到N-si个si
然后后续还pi+1到s后续都OK整体代码就是这样的
//优化DP public boolean isMatchDP2(String s, String p) { if (s.equals("") && p.equals("")) return true; if (p.equals("")) return false; //如果s空，但是p是一堆星，是可以哦，过滤别错了 char[] str = s.toCharArray(); char[] ptr = p.toCharArray(); int N = str.length; int M = ptr.length; boolean[][] dp = new boolean[N + 1][M + 1]; //1）base case：当si==N，越界了 //s的si--N-1就是空串“” //什么情况下能被p从pi--M-1范围匹配出来 //首先pi=M，p的pi--M-1就是空串“”，肯定可以配出来的，此刻s=p //其次，pi=后面一串，需要想办法变空，才能变成空串“”，匹配s的si--N-1， //所以必须得让pi=星才行，这样才能让星变出来“”空串，而且， //与此同时，保证pi+1--M位置也必须能匹配，同时满足上面的条件，才能OK dp[N][M] = true; for (int pi = M - 1; pi >= 0; pi--) { dp[N][pi] = ptr[pi] == '*' && dp[N][pi + 1];//后续也得配出空串 } //（2）si就没到结尾，还有东西，你瞅瞅pi=M吗？ //如果pi=M，那不好意思，p的pi--M-1就是空串啊“”，不可能生出s的si--N-1的，返回false // dp[N][M] = true;上面有了哦 //剩下的默认dpij就是false for (int si = N - 1; si >= 0; si--) { for (int pi = M - 1; pi >= 0; pi--) { //暴力递归怎么写，就怎么改 //（3）si没到结尾，且pi也没有到结尾，有戏了 //那就要看pi能不能匹配出si了 //如果此时si与pi压根没法匹配，那不好意思，不行的 if (str[si] != ptr[pi] && ptr[pi] != '?' && ptr[pi] != '*') { dp[si][pi] = false; //要return的地方，continue continue; } //（4）可能pi字符就是si字符，同时保证p的pi+1--M-1匹配出s的si+1--N-1即可 //可能pi是？，可以变si，同时保证p的pi+1--M-1匹配出s的si+1--N-1即可 if (str[si] == ptr[pi] || ptr[pi] == '?') { dp[si][pi] = dp[si + 1][pi + 1]; continue; } //pi既不是si，也不是？而是星 //那就要看pi能不能匹配出si，或者si--某一段了 //此刻pi已经是*了 //可以让*先变空试试：跟下面i=0长度融合，空串 //该怎么枚举怎么枚举 for (int i = 0; i < N - si; i++) {//最大能匹配si--N，N-si长度 //这里要改改，不要弄si了，应该是星替换s多长的字符，剩下的继续陪 //枚举每一个子串，pi处的星变si--si+i范围上之后，后续能匹配吗？ if (dp[si + i][pi + 1]) { dp[si][pi] = true;//有一个能匹配就算OK //然后不要了 break; } } //上面所有办法试了不行，默认就是了return false; } } return dp[0][0];//s整个范围到p的整个范围能匹配吗？ }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
测试：
public static void test(){ String s = "adceb"; String p = "*a*b"; Solution solution = new Solution(); System.out.println(solution.isMatch(s, p)); System.out.println(solution.isMatchDP(s, p)); System.out.println(solution.isMatchDP2(s, p)); s = "aa"; p = "*aa*b"; System.out.println(solution.isMatch(s, p)); System.out.println(solution.isMatchDP(s, p)); System.out.println(solution.isMatchDP2(s, p)); s = "aa"; p = "*"; System.out.println(solution.isMatch(s, p)); System.out.println(solution.isMatchDP(s, p)); System.out.println(solution.isMatchDP2(s, p)); s = "cb"; p = "?b"; System.out.println(solution.isMatch(s, p)); System.out.println(solution.isMatchDP(s, p)); System.out.println(solution.isMatchDP2(s, p)); s = "acdcb"; p = "a*c?b"; System.out.println(solution.isMatch(s, p)); System.out.println(solution.isMatchDP(s, p)); System.out.println(solution.isMatchDP2(s, p)); s = ""; p = "*****"; System.out.println(solution.isMatch(s, p)); System.out.println(solution.isMatchDP(s, p)); System.out.println(solution.isMatchDP2(s, p)); } public static void main(String[] args) { test(); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
true true true false false false true true false true true true false false false true true true- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
LeetCode测试：
这好像跟暴力没区别，看来还需要优化啊
笔试最优解：优化枚举行为！任何动态规划，如果遇到for循环，想尽一切办法观察dp表在ij上的依赖，然后省掉枚举行为
我们看上面的枚举：
for (int i = 0; i <= N - si; i++) {//最大能匹配si--N，N-si长度 //这里要改改，不要弄si了，应该是星替换s多长的字符，剩下的继续陪 //枚举每一个子串，pi处的星变si--si+i范围上之后，后续能匹配吗？ if (dp[si + i][pi + 1]) { dp[si][pi] = true;//有一个能匹配就算OK //然后不要了 break; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
显然si，pi格子需要依赖
下面这些绿色格子：
而x格子需要依赖红色那些格子
所以呢，si，pi万泉河可以化为：x或上si,pi+1那个绿色格子呗dp[si][pi] = dp[si + 1][pi] || dp[si][pi + 1]; //省掉枚举了 if (dp[si][pi]) continue;- 1
- 2
- 3
代码优化为：
//优化DP:枚举行为优化 public boolean isMatchDP3(String s, String p) { if (s.equals("") && p.equals("")) return true; if (p.equals("")) return false; //如果s空，但是p是一堆星，是可以哦，过滤别错了 char[] str = s.toCharArray(); char[] ptr = p.toCharArray(); int N = str.length; int M = ptr.length; boolean[][] dp = new boolean[N + 1][M + 1]; //1）base case：当si==N，越界了 //s的si--N-1就是空串“” //什么情况下能被p从pi--M-1范围匹配出来 //首先pi=M，p的pi--M-1就是空串“”，肯定可以配出来的，此刻s=p //其次，pi=后面一串，需要想办法变空，才能变成空串“”，匹配s的si--N-1， //所以必须得让pi=星才行，这样才能让星变出来“”空串，而且， //与此同时，保证pi+1--M位置也必须能匹配，同时满足上面的条件，才能OK dp[N][M] = true; for (int pi = M - 1; pi >= 0; pi--) { dp[N][pi] = ptr[pi] == '*' && dp[N][pi + 1];//后续也得配出空串 } //（2）si就没到结尾，还有东西，你瞅瞅pi=M吗？ //如果pi=M，那不好意思，p的pi--M-1就是空串啊“”，不可能生出s的si--N-1的，返回false // dp[N][M] = true;上面有了哦 //剩下的默认dpij就是false for (int si = N - 1; si >= 0; si--) { for (int pi = M - 1; pi >= 0; pi--) { //暴力递归怎么写，就怎么改 //（3）si没到结尾，且pi也没有到结尾，有戏了 //那就要看pi能不能匹配出si了 //如果此时si与pi压根没法匹配，那不好意思，不行的 if (str[si] != ptr[pi] && ptr[pi] != '?' && ptr[pi] != '*') { dp[si][pi] = false; //要return的地方，continue continue; } //（4）可能pi字符就是si字符，同时保证p的pi+1--M-1匹配出s的si+1--N-1即可 //可能pi是？，可以变si，同时保证p的pi+1--M-1匹配出s的si+1--N-1即可 if (str[si] == ptr[pi] || ptr[pi] == '?') { dp[si][pi] = dp[si + 1][pi + 1]; continue; } //pi既不是si，也不是？而是星 //那就要看pi能不能匹配出si，或者si--某一段了 //此刻pi已经是*了 //可以让*先变空试试：跟下面i=0长度融合，空串 //该怎么枚举怎么枚举 dp[si][pi] = dp[si + 1][pi] || dp[si][pi + 1]; //省掉枚举了 if (dp[si][pi]) continue; //上面所有办法试了不行，默认就是了return false; } } return dp[0][0];//s整个范围到p的整个范围能匹配吗？ }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
测试：
public static void test(){ String s = "adceb"; String p = "*a*b"; Solution solution = new Solution(); System.out.println(solution.isMatch(s, p)); System.out.println(solution.isMatchDP(s, p)); System.out.println(solution.isMatchDP2(s, p)); System.out.println(solution.isMatchDP3(s, p)); s = "aa"; p = "*aa*b"; System.out.println(); System.out.println(solution.isMatch(s, p)); System.out.println(solution.isMatchDP(s, p)); System.out.println(solution.isMatchDP2(s, p)); System.out.println(solution.isMatchDP3(s, p)); s = "aa"; p = "*"; System.out.println(); System.out.println(solution.isMatch(s, p)); System.out.println(solution.isMatchDP(s, p)); System.out.println(solution.isMatchDP2(s, p)); System.out.println(solution.isMatchDP3(s, p)); s = "cb"; p = "?b"; System.out.println(); System.out.println(solution.isMatch(s, p)); System.out.println(solution.isMatchDP(s, p)); System.out.println(solution.isMatchDP2(s, p)); System.out.println(solution.isMatchDP3(s, p)); s = "acdcb"; p = "a*c?b"; System.out.println(); System.out.println(solution.isMatch(s, p)); System.out.println(solution.isMatchDP(s, p)); System.out.println(solution.isMatchDP2(s, p)); System.out.println(solution.isMatchDP3(s, p)); s = ""; p = "*****"; System.out.println(); System.out.println(solution.isMatch(s, p)); System.out.println(solution.isMatchDP(s, p)); System.out.println(solution.isMatchDP2(s, p)); } public static void main(String[] args) { test(); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
true true true true false false false false true true true true true true true true false false false false true true true- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
LeetCode测试：
总结
提示：重要经验：1）关键要分清pi的状况，看看能否从pi–M-1上优化出s的si–N-1来，搞清楚base case，和各种可能的情况就好办了
2）暴力递归就是一种很好的尝试，本题还需要改记忆化搜索算法，然后优化精细化DP，有枚举行为，直接优化，老牛逼了！
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。 -
相关阅读:
【Axure高保真原型】输入宽高控制图片尺寸
润石科技（RUNIC）汽车电子应用方案和物料选型
打造“共富果园” 广东乳源推动茶油全产业链高质量发展
【初阶数据结构】单链表(C语言实现+动图演示)
Ensemble learning集成学习（Trees, Forests, Bagging, and Boosting）
Unity中Shader模板测试使用到的二进制
[语音识别] 基于Python构建简易的音频录制与语音识别应用
软件测试/测试开发丨利用ChatGPT编写测试用例
selenium.common.exceptions.WebDriverException: Message: ‘chromedriver’ executable needs to be in PAT
Spring Boot多线程详解
- 原文地址：https://blog.csdn.net/weixin_46838716/article/details/125464536