一道字符串填充算法题

偶然在idailylife的博客上看到Indeed Tokyo 笔试题一道，觉得很有趣，就思考了下这题，这里记录一下。

问题描述

输入字符串str=a[0] a[1] ... a[N]，其中0<N<=10^5。字符串的每一位是0-9或?，需要用0-9填充各个问号的值，使得整个字符串成为一个数（允许前导0），并且满足任意连续10位上的字符(或理解成数字)a[i] a[i+1] ... a[i+9]不重复，输出解的个数。

例如，输入"04??2?7"，输出应当为120.

解题思路

使用回溯法暴力求解显然是不可行的，原文中作者给出了一个很好的做法：只计算str前10个字符有多少可能性。这是基于以下原理的：

对任意区间a[k] a[k+1] ... a[k+9]，题目要求数字均不重复，而且一共也只有10个数字可以选择，故此区间内肯定用完了所有数字。下面将此区间向前移动一步，得到a[k+1] a[k+2] ... a[k+9] a[k+10]，对比两个区间易知，要满足条件只能是a[k] = a[k+10]。由于k是任选的，故可以得到结论：此序列是一个以10为周期的周期序列。

原文中作者实际去填充了前10个字符中的空位，然后来依次判断每种情况的有效性，其实这是完全没有必要的，还有一种更高效的解法。假设a[k]为?，若任意a[k + 10n]不为?的话，？的值其实是可以唯一确定的。用此方法可以先排除一些能唯一确定的?，之后考虑前10个字符中剩余的?，这是一个简单的排列组合问题，不需要实际进行填充即可算出一共有几种填法。具体实现方法见下面的代码。

另外，下面的代码中假设给出的字符串中已经有的数字是符合要求的，这样就可以不对已有数字进行有效性检验。

扩展：这里之所以有如此巧妙的解法，关键在于可能填入的字符数量正好等于不重复区间长度，若二者不等该如何解决呢？这个问题之后有空可以再来思考下。

实现代码

int FillStringNum(char * str, int n) {
    int Q = 0;
    int k;
    int result;

    if (n < 10) {
        for (int i = 0; i < n; i++) {
            if (str[i] == '?') {
                Q++;
            }
        }
        if (Q == 0) {
            return 0;
        }
        else {
            result = 1;
        }
        // 计算排列A(10-(n-Q), Q)
        for (int i = 0; i < Q; i++) {
            result *= (10 + Q - n - i);
        }
        return result;
    }

    for (int i = 0; i < 10; i++) {
        if (str[i] != '?') {
            continue;
        }
        
        for (k = i + 10; k < n; k += 10) {
            if (str[k] != '?') {
                k = 0;
                break;
            }
        }
        if (k > 0) {
            Q++;
        }
    }

    if (Q == 0) {
        return 0;
    }
    else {
        result = 1;
    }

    // 计算排列A(Q, Q) = Q!
    while (Q > 1) {
        result *= Q;
        Q--;
    }

    return result;
}