这篇博文我们探讨一下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的替代字符使用
[代码1]
public static void returnAll(String input) {
if(input == null || input.isEmpty()) {
return;
}
StringBuilder current_string = new StringBuilder();
returnAllRecursion(input, 0, current_string);
}
public static void returnAllRecursion(String input, int current_location, StringBuilder current_string){
if (input.length() == current_location) {
System.out.println(current_string);
return;
}
while (input.length() > current_location && input.charAt(current_location) != '?') {
current_string.append(input.charAt(current_location));
current_location++;
}
if (input.length() == current_location) {
System.out.println(current_string);
current_string.deleteCharAt(current_location - 1);
return;
}
if (input.charAt(current_location) == '?') {
current_string.append(0);
returnAllRecursion(input, current_location + 1, current_string);
current_string.deleteCharAt(current_string.length() - 1);
current_string.append(1);
returnAllRecursion(input, current_location + 1, current_string);
current_string.deleteCharAt(current_string.length() - 1);
}
}
public static void main(String[] args) {
returnAll("0100");
System.out.println("---------------");
returnAll("01??");
System.out.println("---------------");
returnAll("???0");
System.out.println("---------------");
returnAll("????");
}
[思路2]
为什么要提出思路2呢？因为recursive call消耗大量stack空间，所以有时面试官要求不用recursive求解。
其实，大家知道recursive call原理就是用stack来储存function call信息，那我们就可以用stack来模拟compiler做的事情。而且，我们只在stack里存贮我们需要的信息，比如这道题目里存贮究竟?字符是当作0还是1，然后用stack入栈模拟我们进到更深的一级recursive call，而用出栈模拟我们退到上一层
[代码2]
public static void returnAllUsingStack(String input) {
if(input == null || input.isEmpty()){
return;
}
Stack positionToReVisit = new Stack();
positionToReVisit.push(-1);
StringBuilder currentString = new StringBuilder();
int currStartPosition = 0;
for (int i = 0; i < input.length(); i++) {
if (input.charAt(i) == '?') {
positionToReVisit.push(i);
currentString.append(0);
break;
}
currentString.append(input.charAt(i));
currStartPosition++;
}
if (currentString.length() == input.length()) {
System.out.println(currentString);
return;
}
while (!positionToReVisit.isEmpty()) {
for (int i = currStartPosition + 1; i < input.length(); i++) {
if (input.charAt(i)== '?') {
currentString.append('0');
positionToReVisit.push(i);
} else {
currentString.append(input.charAt(i));
}
}
if (currentString.length() == input.length()) {
System.out.println(currentString);
}
currStartPosition = positionToReVisit.pop();
if (currStartPosition == -1) break;
currentString = new StringBuilder(currentString.substring(0, currStartPosition));
currentString.append('1');
}
return;
}
[思路3]
其实这个题目完全可以像解决powerset一下，列举出所有的2^n种可能性。
[代码3]
public static void matchingQuestionMark(String s) {
if (s == null || s.isEmpty()) return;
List questionMarkIndex = new ArrayList();
int totalQuestionMarkCount = 0;
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == '?') {
totalQuestionMarkCount++;
questionMarkIndex.add(i);
}
}
if (totalQuestionMarkCount == 0) return;
for (int i = 0; i < (1 << totalQuestionMarkCount); i++) {
StringBuilder sb = new StringBuilder(s);
int j = 0;
int temp = i;
while (j < totalQuestionMarkCount) {
int index = questionMarkIndex.get(j);
if ((temp & 1) == 0) {
sb.replace(index, index + 1, "0");
} else {
sb.replace(index, index + 1, "1");
}
j++;
temp = temp >> 1;
}
System.out.println(sb.toString());
}
}
