Indeed Tokyo 笔试题一道

Indeed的笔试一次一共4道，鄙人第一次做，前三题1hr就搞定了，唯独最后一题百思不得其解，后来看了大神的思路后幡然醒悟，确实脑子没转过来啊！
题目大致如下：
输入字符串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.
 
最简单的思路当然是回溯，回溯用递归的话容易爆栈，可以自己定义栈结构。但实现完了我发现效率太低了。这种解法的时间复杂度是O(N!).
网上给了一个十分简单的思路：只计算str前10个字符有多少可能性。
这样做可行否？不妨试试看。
假设已经知道了前10个字符a[0]…a[9]能得到解的数目（定作M），那么根据规则，在a[10]的时候要考虑a[1]…a[9]的情况，对于每一种a[1]到a[9]的情况而言，由于已经决定了9个数字了，那么第10个数字显然已经确定了。从这我们可以知道，解的个数肯定是不大于M的，因为假设a[10]不是个”?”并且a[10]又不等于缺的那个数字的话，那这个case是要被毙掉的。然后以此类推，检测a[11], a[12], .. a[N]. 按照这种算法，整个问题的时间复杂度是O(10! * N)=O(N).
==更新==
还有一个更高效的解法，主要思路是利用后面“循环数”得到的确定信息来填充前面的?，然后直接计算组合数即可。具体可以看http://gaomf.cn/2016/10/26/String_Fill/
========
伪代码如下：

输入：长度为N的字符串str
步骤：
0. result_count=0
1. 检查前10个字符str[0]...str[9]中数字冲突情况:
  1.1 若有冲突，return 0
2. 求出所有填充str[0...9]中'?'的方法solution_m=[str[0],...,str[9]]
  foreach solution_m:
    for index = 10,...N-1:
      if str[index]=='?':
        continue # 查找下一个
      else if str[index] == solution_m[index%10]:
        continue # 查找下一个
      else
        break # 这个solution无法满足限制
    if solution_m 通过检查:
      result_count++
输出: 满足条件的solution计数result_count

换个说法就是，后面的数字肯定是前面10个数字的循环，因为新加的a[i]肯定是得顶替上a[i-10]的位置的。