【肝了好多天!】-动态规划十连-超细腻解析——《我的Java打怪日

No.8

这道题跟第五题很类似，如果看懂了第五题，那么这题肯定是信手拈来????????

\### leecode 44. 通配符匹配

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

'?' 可以匹配任何单个字符。

'*' 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

说明:

s 可能为空，且只包含从 a-z 的小写字母。

p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

示例 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.1. 动态规划组成部分1：确定状态

简单的说，解动态规划的时候需要开一个数组，数组的每个元素f[i]或者fi代表什么，类似数学题中x, y, z代表什么

wc，你倒是说说怎么确定要用动态规划来做啊？

- 看题目，需要逐步验证最长长度

- 没有时间复杂度空间复杂度限制，你可以选择 =On的

- 跟前面题很类似，这里需要考虑* 和 ？的情况。

- 尝试根据步骤写出转移方程

在这道题中，我们定义fi 表示字符串 s 的前 i 个字符与 字符串p的前 j 个字符是否匹配

解动态规划需要两个意识：

- 最后一步

- 子问题

最后一步

我们用示例来讲解 ：s = "aaab" p = "aa*b"

根据题目意思，我们知道s和p要全匹配，我们直接用s去匹配p字符串的每一个字符，这样我们的最后一步就是用s字符串中的b字符去匹配p字符串的每一个字符，匹配最后一个字符为b是否相等。

子问题

这是 ' 动态规划Day two - 正则表达式匹配' 的子问题分析

有几种情况需要讨论，也就是用s去匹配p最后一个匹配的字符j

- 如果都是字符，只需要判断：fi = fi-1

- 如果是“.” ,说明可以匹配s的最后任意一个字符，也只需：

fi = fi-1

- 如果是“*”，分两种情况一种是匹配零个字符，一种是匹配1个或多个字符

如果是匹配零个字符：fi = fi ，因为如果j是*，我们就可以对p的j-1匹配任意次数，当然零次就是j-2了。

如果是匹配1个或多个字符：fi = fi-1，匹配 s 末尾的一个字符，将该字符扔掉，而该组合还可以继续进行匹配,简单点说，零个我们判定了，如果是一个我们扔掉一个字符，如果能匹配则保存，如果匹配两个，我们是知道匹配s的上一个字符的结果的，直接匹配就行，同样匹配多个也是如此。（匹配多个是根据前一个的匹配结果得出来的）

这道题基本上是如出一辙

有几种情况需要讨论，也就是用s去匹配p最后一个匹配的字符j

- 如果都是字符，只需要判断：fi = fi-1

- 如果是“？” ,说明可以匹配s的最后任意一个字符，也只需：

fi = fi-1

- 如果是“”，分两种情况，第一种是不需要使用,第二种是需要使用*

实例 ：s = "abc" p = "a*"。

在对s串的a遍历p串的*时，刚好满足dpi = dpi 此时i=1,j=2,

dp1 = dp1=true。 ---不需要使用*

在对s串的b遍历p串的时，刚好满足dpi = fi-1,因为是可以匹配任意一个字母的。

dp2 = dp1=true。---需要使用*

在对s串的c遍历p串的时，刚好满足dpi = fi-1,因为是可以匹配任意一个字母的。

dp3 = dp2=true。---不需要使用*

1.2. 动态规划组成部分2：转移方程

转移方程可以详见子问题分析

1.3. 动态规划组成部分3：初始条件和边界情况

因为要涉及到i-1和j-1，注意边界

boolean[][] f = new booleanm + 1;

f0=true

当f0时，需要判断j是否为，因为可以匹配null串

1.4. 动态规划组成部分4：计算顺序

用s串的每一个字符去匹配p串的每一个字符

它的时间复杂度是Onm,空间复杂度也是Onm

参考代码

public boolean isWildcardMatch(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 ++i) {
? if (p.charAt(i - 1) == '*') {
? dp[0][i] = true;
? } else {
? break;
? for (int i = 1; i ++i) {
? for (int j = 1; j ++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];

本文转自网络，原文链接：https://developer.aliyun.com/article/785640
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！