这篇博文我们探讨一下regular expression matching interview question正则表达式面试的问题,我们先由一道简单的题入手
包子IT面试培训 助你拿到理想的offer!
有问题,问包子!Got question? Ask Baozi!
[例题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("????"); }regular expression matching interview question 正则表达式面试的问题
[思路2]
为什么要提出思路2呢?因为recursive call消耗大量stack空间,所以有时面试官要求不用recursive求解。
其实,大家知道recursive call原理就是用stack来储存function call信息,那我们就可以用stack来模拟compiler做的事情。而且,我们只在stack里存贮我们需要的信息,比如这道题目里存贮究竟?字符是当作0还是1,然后用stack入栈模拟我们进到更深的一级recursive call,而用出栈模拟我们退到上一层
[代码2]
regular expression matching interview question 正则表达式面试的问题 [思路3]
其实这个题目完全可以像解决powerset一下,列举出所有的2^n种可能性。
[代码3]
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;
}
regular expression matching interview question 正则表达式面试的问题 [思路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()); } }
我们会在后面的blog里继续探讨regular expression matching interview question 正则表达式面试的问题,希望大家继续关注我们!