博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Regular Expression Matching leetcode
阅读量:4620 次
发布时间:2019-06-09

本文共 993 字,大约阅读时间需要 3 分钟。

递归方法运行时间过长。考虑使用动态规划的方法。

代码如下:

bool isMatch(string s, string p) {        int i,j;        int m=s.size();        int n=p.size();         bool b[m + 1][n + 1]; // b[i][j]表示s[i-1]和p[j-1]的匹配结果        b[0][0] = true;          for (i = 0; i < m; i++) {              b[i + 1][0] = false;          }                 for (j = 0; j < n; j++) {              b[0][j + 1] = j > 0 && '*' == p[j] && b[0][j - 1];          }            for (i = 0; i < m; i++) {              for (j = 0; j < n; j++) {                  if (p[j] != '*') {                      b[i + 1][j + 1] = b[i][j] && ('.' == p[j] || s[i] == p[j]);  //表达式中的b[i][j]的意思是:s[i-1]已经和p[j-1]匹配。下同。                } else {                      b[i + 1][j + 1] = b[i + 1][j - 1] && j > 0 || b[i + 1][j] ||                                  b[i][j + 1] && j > 0 && ('.' == p[j - 1] || s[i] == p[j - 1]);  //别分为*之前的字符匹配零次、一次、多次                }              }          }          return b[m][n];      }

 

转载于:https://www.cnblogs.com/coderht/p/5364707.html

你可能感兴趣的文章
Java 处理 XML 的三种主流技术及介绍
查看>>
nodejs框架express4.2 简单入门
查看>>
java exec python program
查看>>
windows防火墙命令详解
查看>>
【分治】简单说说快排
查看>>
A1117.Eddington Number
查看>>
如何预览将要上传的图片-使用H5的FileAPI
查看>>
ubuntu安装wine+plsql
查看>>
某谷 P5153 简单的函数
查看>>
sizzle源码分析 (4)sizzle 技术总结及值得我们学习的地方
查看>>
ECMAScript6词法
查看>>
ASP.NET Core 中文文档 第四章 MVC(3.1)视图概述
查看>>
软件工程项目之摄影App(第二次冲刺)
查看>>
Struts常见默认值重写
查看>>
iOS9的一些问题
查看>>
maven3 下载列表
查看>>
9.22作业3
查看>>
LeetCode Ones and Zeroes
查看>>
求余符号的用法
查看>>
C语言文件操作函数(ANSI)详解(一)
查看>>