Regular Expression Matching Problems 1

包子IT面试培训 助你拿到理想的offer!

有问题，问包子！Got question? Ask Baozi!

这篇博文我们探讨一下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());
        }
    }