一道字符串填充算法题

偶然在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个字符中剩余的?,这是一个简单的排列组合问题,不需要实际进行填充即可算出一共有几种填法。具体实现方法见下面的代码。

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

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

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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;
}
文章目录
  1. 1. 问题描述
  2. 2. 解题思路
  3. 3. 实现代码