Regular Expression Matching Problems 1

这篇博文我们探讨一下regular expression matching的问题,我们先由一道简单的题入手

[例题1]

Given a string of 1, 0 or ?, return all the matching strings that ? could be either 0 or 1.

For example,

input : 1??

output: {100, 101, 110, 111}.

input: 100100?00?

output: {1001000000,1001000001,1001001000,1001001001}

[思路1]

我们最直观的想法就是逐个字符扫描input. 当input里字符是0或者是1就原样输出. 问题在于当字符是?时我们该怎样处理. 这里就用到recursive编程方法最基本的套路:

分支加存储

所 谓分支就是定义一个recursive function,让它的param list包含input和下一个input里访问字符的位置。当遇到可wild card字符时,对于wild card可替换的每一个字符,都call一下recursive function。所谓存储就是把这些用不同字符替代的情况都存储起来。一般来说,可以在param list加一个string表示部分结果。这样当我们访问完input里最后一个字符以后,输出该部分结果(现在是一个有效结果)。而且,当每一层 recursive call返回以后,都删除这个recursive call所产生的替代字符,以便下一个recurisve call的替代字符使用

原文发布于微信公众号 - 包子铺里聊IT(baozitraining)

原文发表时间:2014-09-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏测试驿栈

Jmeter(五)_函数

1、它有两个参数,第一个参数是要执行的语句,可以是beanshell语句或者是文件地址,是必选参数;第二个参数是保存结果的变量名称,非必选参数。

1982
来自专栏FreeBuf

从反射链的构造看Java反序列漏洞

概况 今天我想从构造反射链的从无到有到被利用来谈谈java的反序列化漏洞,从反射的最开始到执行payload,一个从无到有的过程,首先我们介绍一下Transfo...

2789
来自专栏前端侠2.0

atob和btoa的趣谈 原

不了解的人突然看到window对象的atob和btoa 函数,估计会认为哪个臭小子添加全局函数了。

1512
来自专栏Jackson0714

C#多线程之旅(4)——APM初探

41213
来自专栏云霄雨霁

Java--类和对象之基础知识

1573
来自专栏郭少华

ES6

在cmd命令窗口初始化项目-y代表全部默认同意,就不用一次次按回车了。命令执行完成后,会在项目根目录下生产package.json文件。

1713
来自专栏java工会

JAVA 同步实现原理

Synchronized是Java中解决并发问题的一种最常用的方法,也是最简单的一种方法。Synchronized的作用主要有三个:

630
来自专栏达摩兵的技术空间

js中的作用域

相信自从es6出来之后,你一定多少知道或者已经在项目中实践了部分的块级作用域,在函数或者类的内部命名变量已经在使用let了,但是你知道它真正的作用是什么吗?又是...

1342
来自专栏ShaoYL

iOS循环引用

3035
来自专栏IT探索

g++&&gcc

3.C++:在构造函数中,当使用初始化列表来初始化成员变量时,如果初始化顺序与定义成员变量的顺序不一致,当使用-Wreorder选项时,会重新调整顺序初始化顺序...

741

扫码关注云+社区

领取腾讯云代金券