柳江企业网站建设价格,wordpress网站打不开,抖音挂小程序怎么赚钱,公众号开发者密码是什么意思一、题目概述 二、思路方向 在Java中#xff0c;实现一个支持.和*的正则表达式匹配器#xff0c;可以通过递归或动态规划#xff08;DP#xff09;的方法来完成。这里#xff0c;我将使用动态规划的方法来解决这个问题#xff0c;因为它更容易理解和实现。 动态规划的思…一、题目概述 二、思路方向 在Java中实现一个支持.和*的正则表达式匹配器可以通过递归或动态规划DP的方法来完成。这里我将使用动态规划的方法来解决这个问题因为它更容易理解和实现。 动态规划的思路是我们可以创建一个二维的布尔数组dp其中dp[i][j]表示字符串s的前i个字符和模式p的前j个字符是否匹配。初始化时dp[0][0]为true空字符串和空模式匹配而dp[0][j]对于所有j 0只有在p的前j个字符都是*时才为true因为*可以匹配零个字符。 接下来我们遍历dp数组填充剩余的条目。对于每个(i, j)我们考虑以下情况 如果p[j-1]不是*那么dp[i][j]为真当且仅当s[i-1] p[j-1]或p[j-1] .且dp[i-1][j-1]为真。如果p[j-1]是*那么有两种可能性 忽略*和前面的字符即看dp[i][j-2]。匹配零个或多个前面的字符这取决于dp[i-1][j]如果s[i-1]匹配p[j-2]则可以通过添加s[i-1]到匹配中为真。 三、代码实现
public class Solution { public boolean isMatch(String s, String p) { int m s.length(); int n p.length(); // 创建一个二维布尔数组dp boolean[][] dp new boolean[m 1][n 1]; dp[0][0] true; // 空字符串和空模式匹配 // 初始化dp[0][j]只有当p全是*时才匹配 for (int j 1; j n; j) { if (p.charAt(j - 1) *) { dp[0][j] dp[0][j - 2]; } } // 填充dp数组 for (int i 1; i m; i) { for (int j 1; j n; j) { if (p.charAt(j - 1) ! *) { dp[i][j] (s.charAt(i - 1) p.charAt(j - 1) || p.charAt(j - 1) .) dp[i - 1][j - 1]; } else { // 两种情况匹配0次或多次前面的字符 dp[i][j] dp[i][j - 2]; // 忽略*和前面的字符 if (s.charAt(i - 1) p.charAt(j - 2) || p.charAt(j - 2) .) { dp[i][j] dp[i][j] || dp[i - 1][j]; } } } } return dp[m][n]; } public static void main(String[] args) { Solution solution new Solution(); System.out.println(solution.isMatch(aa, a)); // false System.out.println(solution.isMatch(aa, a*)); // true System.out.println(solution.isMatch(ab, .*)); // true System.out.println(solution.isMatch(aab, c*a*b)); // true System.out.println(solution.isMatch(mississippi, mis*is*p*.)); // false }
}
执行结果 四、小结 这个实现通过动态规划解决了正则表达式的匹配问题时间复杂度为O(mn)空间复杂度也为O(mn)其中m和n分别是字符串s和模式p的长度。 结语 因为遇见你我才知道我也能具有美丽的记忆。 所以无论你怎样对待我 我都会用心去宽恕你的恨 用心去铭记你的好
