C++ 数组实现整数模板匹配计数

题目描述

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

一个正整数(严格大于 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 100 90 100

算法1

(暴力枚举) O(n^2)

// C++ 代码实现

时间复杂度

参考文献

算法2

(暴力枚举) O(n^2)

// C++ 代码实现

时间复杂度

参考文献