杂志媒体网站建设方案软件商店网页版

杂志媒体网站建设方案,软件商店网页版,深圳网站建设设计,恩施网站建设题目要求是给一个字符串和一个表达式字符串#xff0c;要让表达式字符串通过给定的规则#xff0c;完全的匹配字符串#xff0c;俩个字符串中的所有字符都要使用到对于给的这个字符串规则#xff0c;有几点重要. 是必须要匹配一个字符 aa ... 是匹配不上的* 这个字符前面一…题目要求是给一个字符串和一个表达式字符串要让表达式字符串通过给定的规则完全的匹配字符串俩个字符串中的所有字符都要使用到对于给的这个字符串规则有几点重要. 是必须要匹配一个字符 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] truedp[x][0] 表示表达式字符串为空 那么一个都匹配不上所以全为falsedp[0] 表示需要匹配的字符串为空 应为有 a* 这种在 它可以表示空 所以需要给特殊处理为为truedp[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小时 这真是我做过的最难的动态规划题 且时最难的递归题挺有意思的 尤其是最后的为空的特殊处理给我迷了好一会