题目：过年了，考拉哥哥搞了一批礼品券出售。每张礼品券上有个涂层，用户刮开涂层后，将涂层背后的16位卡密输入到考拉就可以兑换相应的券。在印刷礼品券的时候，印刷出来后我们才发现印刷的g和9长的一摸一样。此时，后台数据库由于对卡密做了三次加密无法破解，卖出去的礼品券无法收回。为了保证礼品卡能正常使用，我们的解决方案如下，即对所有的g和数字9进行模糊匹配（已验证该方案下当前批次的礼品券卡密不会出现重复）。现在要求，用户输入一串十六位的卡密，找出所有相似的卡密。即如果用户输入是99xxx,则卡密ggxxx,g9xxx,9gxxx,99xxx都应匹配。

解题思路: 忽略其他客观因素，此题基本就是求所有g和9位置替换成9或g的排列组合，举例9gxx，如图一所示，所有可能组合为如下二叉树的路径组合(向左走为9，向右走为g，二叉树深度即为9和g
的数目)，所以此题基本抽象为二叉树的遍历。最优解为通过使用位运算(如图2所示，假设9等同于0，g等同于1，那么所有组合为0到3的所有二进制表示)；普通解法为递归。

//java code
public static String[] getSimilarVoucher(char[] code){
    Integer len = code.length;
    Integer similarNum = 0;
    Integer[] indexString = new Integer[len];

    for (Integer i = 0; i< len;i++) {
        if (code[i] == '9' || code[i] == 'g'){
            indexString[similarNum] = i;
            similarNum++;
        }
    }

    Integer n = 1 << similarNum;
    String[] similarSet = new String[n];

    for ( Integer i = 0; i < n; i++) {
        char[] similarCode = code;
        for (Integer j = 0; j < similarNum; j++ ){
            if ((i & (1 << j)) == 0) {
                similarCode[indexString[j]] = '9';
            }else {
                similarCode[indexString[j]] = 'g';
            }
        }
        similarSet[i] = String.valueOf(similarCode);
    }

    for (Integer i = 0; i < similarSet.length; i++){
        System.out.println(similarSet[i]);
    }
    return similarSet;
}

This article used CC-BY-SA-4.0 license, please follow it.