开发者社区> 答案命运> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

剑指Offer——正则表达式匹配(JS实现)

简介: 剑指Offer——正则表达式匹配(JS实现)
+关注继续查看

题目描述

image.png

解题思路

  • 本题的主流解法包括两种,主要是递归回溯与动态规划,鉴于动态规划不易理解,本文采用递归回溯的方法进行讲解,步骤如下:

1. 判断p字符串是否为空,如果为空则继续判断字符串s是否为空

  • 我们首先要准确理解字符s和字符p的含义,字符s代表的是待匹配的字符串,而字符串p则代表的是我们的匹配模式
  • 如果匹配模式为空,我们要看待匹配的字符s是否为空,如果两者皆为空,说明空匹配空,结果返回true,如果p为空,但是s不为空,说明让空去匹配非空,肯定false,这是我们递归的出口。
if (p.length === 0) {
    if (s.length === 0) {
        return true;
    } else {
        return false;
    }
}

2. 判断在字符串s非空的情况下,第一个字符是否能够成功匹配

  • 为什么要在字符串s非空的情况下,去进行匹配?

答:因为字符串s如果为空,去匹配第一个字符是没有意义的,如果字符s为空,且能够走到这里,说明字符串p不为空,要不然也不能走到第二步就返回了,如果字符s为空我们跳转到后面的第三步。

  1. s的第一个字符和p的第一个字符相等,或者p的第一个字符为 ".",都说明成功匹配到了。
  2. 判断字符串p的长度,此时存在两种情况,一种是小于2,一种是大于等于2,如果小于2,我们就没必要判断当前字符p的第二个字符是不是*号了,直接将s去掉首元素和p去掉首元素,投入到递归函数中去继续判断,如果大于等于2的情况,则是有必要继续判断的,我们要判断p字符的第二个字符是不是*号的,如果第二个是*号则存在两种情况,一个是这个*号代表前面的字符出现了0次,另一种情况是前面的字符出现了多次,此时我们就要分情况讨论了,如果代表的是0次,则将s不变和p去掉前两个字符,投入递归函数,如果代表的是多次,我们首先当作一次,把s去掉首元素,p不变继续递归。
  3. 如果字符串p的长度小于2,由于前面的条件限制使得首元素是相同的,我们只用将s和p分别去掉首元素,继续投入递归,由结束条件来帮助我们继续判断。
  4. 如果字符串s为空,或者第一个字符不匹配,我们首先判断p的长度,如果p的长度是小于2的,当前元素不同,后面又没有*了,所以直接返回false,如果p的长度是大于等于2的,继续判断p的第二个元素是不是*,如果是,则将s不变,p去掉两个首元素继续递归判断,如果第二个元素不是*,直接返回false.

解题代码

var isMatch = function (s, p) {
    // 判断模式p是否为空,如果为空,则判断s是否为空
    if (p.length === 0) {
        if (s.length === 0) {
            return true;
        } else {
            return false;
        }
    }
    // 判断第一个字符是否匹配
    if (s.length !== 0 && (s[0] === p[0] || p[0] === '.')) {
        // 走到这里说明,第一个字符是匹配的
        if (p.length >= 2) {
            // 判断第二个字符是不是 *
            if (p[1] === '*') {
                return isMatch(s, p.slice(2)) || isMatch(s.slice(1), p)
            } else {
                return isMatch(s.slice(1), p.slice(1));
            }
        } else {
            return isMatch(s.slice(1), p.slice(1));
        }
    } else {
        if (p.length >= 2) {
            if (p[1] === '*') {
                return isMatch(s, p.slice(2));
            } else {
                return false;
            }
        } else {
            return false;
        }
        
    }
};

总结(本题给我们的启示思路)

  • 学会通过递归回溯解决多边界条件问题
  • 本题的难点在于*这种情况的考虑,刚开始不会也是正常,千万不要焦躁,不要放弃,仔细想想总会解出来的。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
javascript 验证 yyyy-MM-dd HH:mm:ss 的正则表达式
原文:javascript 验证 yyyy-MM-dd HH:mm:ss 的正则表达式^((\d{2}(([02468][048])|([13579][26]))[\-\/\s]?((((0?[13578])|(1[02]))[\-\/\s]?((0?[1-9])|([1-2][0-9])|(3[0...
1505 0
验证(Javascript和正则表达式)
原文: 验证(Javascript和正则表达式) 昨天写了验证(C#和正则表达式),今天又写了个js版的验证。现在贴出来,为了方便自己查阅,同时也希望能给需要的人帮助和一些启发。
950 0
js验证电子邮箱的正则表达式
function isEmail(mail) { var filter = /^([a-zA-Z0-9_\.\-])+\@(([a-zA-Z0-9\-])+\.)+([a-zA-Z0-9]{2,4})+$/; if (filter.
607 0
Arcgis for Javascript API下类似于百度搜索A、B、C、D marker的实现方式
原文:Arcgis for Javascript API下类似于百度搜索A、B、C、D marker的实现方式 多说无益,首先贴两张图让大家看看具体的效果: 图1、百度地图搜索结果 图2、Arcgis for JavaScript实现的效果 看到了效果,是不是各位有点小鸡动,是不是也宠宠欲动,有木有?但是具体是怎么实现的呢?下面我来详细的给各位说说我的实现思路吧。
1049 0
Ajax PHP JavaScript MySQL实现简易的无刷新在线聊天室
思路 消息显示区 发消息 板块 消息显示 消息发送 优化 显示非重复性的数据 优化显示 加上滚动条 每次都显示最新消息 完整代码 前端代码 数据库表结构 服务器端代码 总结与展望 总结 展望 为更好的运用这两天学到的Ajax的相关的知识,就做了个简单的在线网络聊天室。
1293 0
PHP Ajax JavaScript Json 实现天气信息获取
使用第三方服务 间接方式 思路 使用到的服务 实现代码 前端完整代码 总结 要在自己的网站上添加一个天气预报功能,是一个很普通的需求,实现起来也不是很难。
1552 0
PHP Ajax JavaScript 实现 无刷新附件上传
普通表单 前端页面 后台处理 带有文件的表单 刷新方式 前端界面 后台页面 无刷新方式 大文件上传 POST极值 upload极值 上传细节 前端页面 后台处理 总结 对一个网站而言,有一个基本的不可缺少的功能,那就是文件上传。
1257 0
PHP + JavaScript + Ajax 实现无刷新页面加载效果
数据源工厂 Json生成方式1 Json生成方式2 数据搬运工 数据加工师 转换类型 加工展示 结果展示 初始页面 点击按钮之后 总结 今天这个实验的思路就是实现一个无刷新的页面加载效果。
1184 0
+关注
答案命运
人有多自律,就有多自由!
文章
问答
文章排行榜
最热
最新
相关电子书
更多
Python第五讲——关于爬虫如何做js逆向的思路
立即下载
JS零基础入门教程(上册)
立即下载
编程语言如何演化—— 以 JS 的 private 为例
立即下载