百度建站平台官网,长治推广型网站开发,10g空间网站做视频网站,福田蒙派克配件10.给你一个字符串 s 和一个字符规律 p#xff0c;请你来实现一个支持 . 和 * 的正则表达式匹配。 . 匹配任意单个字符 * 匹配零个或多个前面的那一个元素 所谓匹配#xff0c;是要涵盖 整个 字符串 s的#xff0c;而不是部分字符串。 示例 1#xff1a; 输入#xff1a;s… 10.给你一个字符串 s 和一个字符规律 p请你来实现一个支持 . 和 * 的正则表达式匹配。 . 匹配任意单个字符 * 匹配零个或多个前面的那一个元素 所谓匹配是要涵盖 整个 字符串 s的而不是部分字符串。 示例 1 输入s “aa”, p “a” 输出false 解释“a” 无法匹配 “aa” 整个字符串。 示例 2: 输入s “aa”, p “a*” 输出true 解释因为 * 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此字符串 “aa” 可被视为 ‘a’ 重复了一次。 示例 3 输入s ab, p .* 输出true 解释.* 表示可匹配零个或多个*任意字符.。 首先基本情况就是我们会想到同时遍历两个字符串s 为被匹配字符串p 为正则字符串在匹配过程中 s 是不断往后遍历的但 p 不一定因为 * 和前面的字符组合可以表示多个字符。也就是说我们的匹配过程其实可以认为是不断看 s[:i] 和 p[:j] 是否匹配python 语法就是其实就是字符串前 i-1 位和前 j-1 位dp 的感觉是不是就来了从 s[:1] 和 p[:1]即两个字符串的首位字符 开始匹配每次添加 s 或 p 的一个字符看是否匹配最终得到两个完整字符串是否匹配。那么状态定义就来了设 dp[i][j] 为 s 的前 i 个字符与 p 的前 j 个字符时候匹配。状态转移方程因为 dp[0][0] 对应的是空字符所以需要注意 dp[i][j] 对应的新添加的字符是 s[i - 1] 和 p[j - 1]。上面提到了匹配过程唯一的变数其实就在 p所以以它来划分情况找到 dp[i][j] 和 dp[i-1][j] 或者 dp[i][j-1] 或者 dp[i-1][j-1] 的联系。dp[i][j] 对应的是 s[i-1] 和 p[j-1]我们唯一不确定的其实就是 p 中有没有 . 和 *并且其实 * 包含的情况更多那么我们就把 . 划分到不包含 * 的情况中这里说的包含不是整个字符而是前一个状态是否包含具体继续往下看。要匹配的话首先如果 p[j-1] 为 * 以下三种情况 dp[i][j] 可以匹配成功 dp[i][j-2] 为 true 让 p[j-2] 的某个字符和 p[j-1] 的 * 组合为该字符出现 0 次比如 aa 和 b*aa跳过 b*dp[i-1][j] p[j-2] s[i-1]没加 s[i-1] 之前就匹配了现在让 p[j-2] 和 p[j-1] 组合成s[i-1]*即 p 包含一个或多个 s[i-1] 比如 aaa 和 a* 的匹配dp[i-1][j] p[j-2] .没加 s[i-1] 之前就匹配了现在让 p[j-2] 和 p[j-1] 组合成.*也等于 p 包含一个或多个 s[i-1] 比如 aaa 和 .* 的匹配 如果 p[j-1] 不为 *以下两种情况能匹配成功 dp[i-1][j-1] p[j-1] s[i-1]除了新加的两个字符之前都匹配且新加的两个字符为同一个字符dp[i-1][j-1] p[j-1] .除了新加的两个字符之前都匹配且新加的 p[j-1] 为任意字符 . public boolean isMatch(String s, String p) {int ms.length()1,np.length()1;boolean[][] dp new boolean[m][n];dp[0][0] true;for(int j2;jn;j2)dp[0][j] dp[0][j-2] p.charAt(j - 1) *;for(int i 1; i m; i) {for(int j 1; j n; j) {if(p.charAt(j - 1) *) {if(dp[i][j - 2]) dp[i][j] true; else if(dp[i - 1][j] s.charAt(i - 1) p.charAt(j - 2)) dp[i][j] true;else if(dp[i - 1][j] p.charAt(j - 2) .) dp[i][j] true;} else {if(dp[i - 1][j - 1] s.charAt(i - 1) p.charAt(j - 1)) dp[i][j] true;else if(dp[i - 1][j - 1] p.charAt(j - 1) .) dp[i][j] true;}}} return dp[m-1][n-1];}也可以简化成三元运算和与或运算 public boolean isMatch(String s, String p) {int m s.length() 1, n p.length() 1;boolean[][] dp new boolean[m][n];dp[0][0] true;// 初始化首行for(int j 2; j n; j 2)dp[0][j] dp[0][j - 2] p.charAt(j - 1) *;// 状态转移for(int i 1; i m; i) {for(int j 1; j n; j) {dp[i][j] p.charAt(j - 1) * ?dp[i][j - 2] || dp[i - 1][j] (s.charAt(i - 1) p.charAt(j - 2) || p.charAt(j - 2) .) :dp[i - 1][j - 1] (p.charAt(j - 1) . || s.charAt(i - 1) p.charAt(j - 1));}}return dp[m - 1][n - 1];}
