安康市网站建设_网站建设公司_全栈开发者_seo优化

题目要求是给一个字符串和一个表达式字符串，要让表达式字符串通过给定的规则，完全的匹配字符串，俩个字符串中的所有字符都要使用到

对于给的这个字符串规则，有几点重要

. 是必须要匹配一个字符 aa ... 是匹配不上的

* 这个字符前面一定会有一个字符，他不会单独出现，也不会位于字符首

a* 可以匹配空字符串，也就是说 ab c*ab 也是能匹配上的

.* 他能被翻译 ....... 若干个点也就是可以匹配任意的字符串

那么现在就可以着手开始解这道题了

对于 s 字符串 p 表达式字符串 他俩的匹配

前面的mis都是相同的，而到第一个*时，发现*前面时s 于是s*可以翻译为 空 s ss sss 等，而这些情况是都需要储存下来的，因为*后面的s 是需要找到一个 s* 翻译为 ssss 这个字符串，才能正确的匹配字符串，而我再走到s*翻译时，并不会知道后面的字符串时需要翻译为哪个才能正确表示

所以需要全部储存下来，而这样就有了一个表达式

到p位置的字符串能否翻译 = p 位置 和 s 位置相同 && p 位置之前的字符串 和 s 位置 之前的字符串能匹配上

很容易看出了，动态规划解法，而且需要一个二维的dp表，表示p s字符串的位置，用dp来表示俩字符串的匹配关系

那么dp表定义就有了 dp[m][n] 表示0 - m 长度的字符串 和 0 - n 长度的匹配字符串能否匹配上

比如 dp[2][3] = true 表示 长度为 0 - 2 的 s 字符串 和 长度为 0- 3 的匹配字符串能匹配上

状态方程的推导

整理下 最终的推导方程

初始化

首先多一行多一列防止越界

对边界特殊处理

0 0 位置俩都为空可以被匹配 所以 dp[0][0] = true

dp[x][0] 表示表达式字符串为空 那么一个都匹配不上，所以全为false

dp[0] 表示需要匹配的字符串为空 应为有 a* 这种在 它可以表示空 所以需要给特殊处理为为true

dp[0][2] = true p[0-1] 能翻译为空

dp[0][4] = true p[0-1] 为空 p[2 - 3] 为空

之后越界了 不过如果不为* 就退出处理，因为之后的都匹配不上空的s字符串了

到这就可以开始些代码了

public boolean isMatch1(String ss, String pp) { char[] s = ss.toCharArray(); char[] p = pp.toCharArray(); int m = s.length; int n = p.length; // m 表示 字符串 n 规则 boolean[][] dp = new boolean[m + 1][n + 1]; //只有. 会涉及到 i-1 j-1 dp[0][0] = true; //初始化 因为 a8 可以翻译为空字符串 所以需要特殊处理开头 for(int i = 2; i < n + 1; i += 2){ if(p[i - 1] == '*') dp[0][i] = true; else break; } for(int i = 1; i < m + 1; i++){ for(int j = 1; j < n + 1; j++){ char curS = s[i - 1]; char curP = p[j - 1]; if(curP == '.' || curS == curP){ dp[i][j] = dp[i - 1][j - 1]; }else if(curP == '*'){ dp[i][j] = dp[i][j - 2] || (p[j - 2] == curS || p[j - 2] == '.') && dp[i - 1][j]; } } } return dp[m][n]; }

wok 写了3小时＋ 这真是我做过的最难的动态规划题 且时最难的递归题

挺有意思的 尤其是最后的为空的特殊处理，给我迷了好一会