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的替代字符使用