整数模板匹配计数 - 算法题解 - 常规

整数模板匹配计数 - 算法题解

问题描述：

整数模板是由数字和问号组成的字符串（也可以没有问号）。

一个正整数（严格大于 0）匹配整数模板，如果可以用一个数字替换模板中的每个问号，这样我们就可以得到该整数的十进制表示形式，十进制不能有前导零。

例如：

42 匹配 '4?'
1337 匹配 '????';
1337 匹配 '1?3?';
1337 匹配 '1337';
3 不匹配 '??';
8 不匹配 '???8';
1337 和 '1?7' 不匹配。

你将得到一个最多由 5 个字符组成的整数模板。计算与之匹配的正整数（严格大于 0）的个数。

输入格式 第一行一个整数 t(1≤t≤20)，表示组数。

接下来 t 行，每行一个不超过长度 5 的字符串。

输出格式 对于每个测试用例，输出一个整数，表示与模板匹配的正整数（严格大于 0）的个数。

样例组

输入#1 8 '??' '?' '0' '9' '03' '1??7' '?5?' '9??99'

输出#1 90 9 0 1 0

思路： 枚举每个位置填什么数字，如果匹配就计数。需要注意的是，模板中的数字和填入的数字不能相同。

时间复杂度： $O(10^k)$，其中 $k$ 是模板的长度。

代码实现：

def count_matches(template):
    count = 0
    for i in range(10**len(template)):
        num_str = str(i).zfill(len(template))
        match = True
        for j in range(len(template)):
            if template[j] == '?' and num_str[j] == template[j]:
                match = False
                break
        if match:
            count += 1
    return count

t = int(input())
for _ in range(t):
    template = input()
    print(count_matches(template))

总结： 本题解介绍了整数模板匹配计数问题，并提供了解决该问题的代码实现和时间复杂度分析。该代码采用枚举的方法，时间复杂度为 $O(10^k)$，其中 $k$ 是模板的长度。