YuanBao LeetCode 10.Regular Expression Matching Java Implement-北京尧图网络

Here is a standard Dynamic Programming solution for LeetCode 10 (Regular Expression Matching) in Java.ApproachWe use a 2D boolean array“dp[i][j]” which represents whether the first“i” characters of the string“s” match the first“j” characters of the pattern“p”.Key Rules:Base Case:“dp[0][0] true” (empty matches empty).Pattern ends with“: The” can match zero of the preceding element (“dp[i][j-2]”) OR one/more if the preceding character matches (“dp[i-1][j]”).Normal match /“‘.’”: If characters match or pattern is“‘.’”, carry over the previous state (“dp[i-1][j-1]”).Java Implementationclass Solution {public boolean isMatch(String s, String p) {int m s.length();int n p.length();// dp[i][j] true if first i chars of s match first j chars of p boolean[][] dp new boolean[m 1][n 1]; // 1. Base case: empty string matches empty pattern dp[0][0] true; // 2. Handle patterns like a*, a*b*, a*b*c* matching an empty string for (int j 2; j n; j) { if (p.charAt(j - 1) *) { dp[0][j] dp[0][j - 2]; } } // 3. Fill the DP table for (int i 1; i m; i) { for (int j 1; j n; j) { char currentCharS s.charAt(i - 1); char currentCharP p.charAt(j - 1); // Case A: Current characters match or pattern has . if (currentCharP currentCharS || currentCharP .) { dp[i][j] dp[i - 1][j - 1]; } // Case B: Current pattern character is * else if (currentCharP *) { // * matches zero of the preceding element dp[i][j] dp[i][j - 2]; // * matches one or more of the preceding element // Check if the character before * matches current string char char charBeforeStar p.charAt(j - 2); if (charBeforeStar currentCharS || charBeforeStar .) { dp[i][j] dp[i][j] || dp[i - 1][j]; } } // Case C: Characters dont match else { dp[i][j] false; } } } return dp[m][n]; }}Complexity AnalysisTime Complexity: O(m \times n) , where m is the length of“s” and nis the length ofp. We fill a table of size (m1) \times (n1)$.Space Complexity: O(m \times n) for the DP table. (This can be optimized to O(n) using a 1D array if needed.)Test Cases“s”“p” Output““aa””““a””“false”““aa””““a*””“true”““ab””“”.*“”“true”““aab””““cab””“true”““mississippi””““misisp*.””“false”Would you like me to explain a specific part of the logic in more detail, or provide the space-optimized (1D DP) version?

YuanBao LeetCode 10.Regular Expression Matching Java Implement

相关推荐

C++ 泛型世界的两块拼图：容器适配器与仿函数

【minio】#4 | MinIO API 文件操作

（论文速读）LogSAD：无需训练的结构异常与逻辑异常统一检测

更多资讯

随机蓝屏排查实战：从BlueScreenView到WinDbg的完整追踪记录

OSMDroid切换底图不更新？缓存与刷新机制解析

HAMi在GPU云平台中的共享调度与异构纳管实践

MPS校招笔试全解析：电源管理芯片与BUCK/BOOST考点攻略

OpenClaw实战：从WSL2部署到Ollama本地模型自动化数据提取

HTTP/2与HTTP/3核心机制对比及部署实战指南

今日更新

Multisim仿真NE555 PWM控制器：从搭电路到调占空比全流程

S32K312 AUTOSAR BSW开发实战：从配置踩坑到烧录交付

双目视觉三维人脸重建：从视差图到点云粗配准全流程解析

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？