一个这样的字符串 123**56*8，*表示任意数字（0-9），求这个字符串可能的所有子串。 这样的算法该怎么写？

一个这样的字符串 123**56*8，*表示任意数字（ 0-9 ），求所有符合要求的字符串。

垃圾算法 n^3

一个简单的想法，从前往后，遇到数字，就直接继续下一层递归，遇到通配符，就分成 0-9 递归，直到最后一位输出

你说的是字符串，不是子串吧？把*替换成 0 最小，123005608，替换成 9 最大,123995698。枚举 000-999，填到对应的三个*上不就可以了？

三重循环 0 到 9 呗，这还用啥算法，简直是侮辱算法这个词。

<?php

$template = '123**56*8';
$format = str_replace('*', '%s', $template);

$star_count = substr_count($template, '*');

$end_num = intval(str_repeat('9', $star_count));

for ($i = 0; $i <= $end_num; $i++) {
$num_str = str_pad($i, $star_count, '0', STR_PAD_LEFT);
$args = str_split($num_str, 1);
array_unshift($args, $format);
$fullfill = call_user_func_array('sprintf', $args);
echo $fullfill . PHP_EOL;
}

//全排列问题
//C++

#include <stdio.h>
#include <iostream>

using namespace std;
void permutation(char* a, int k, int m);
// k 为计数器， m 为被交换的序列的长度-1
int main(){
char a[] = "abc";
cout << a << "answer:" << endl;
permutation(a,0,2);
}

void permutation(char* a, int k, int m){
if(k == m){
for(int i = 0; i <= m; i++){
cout << a[i];
}
cout << endl;
}
else {
for(int j = k ; j <= m; j++){
swap(a[j], a[k]);
permutation(a, k + 1, m);
swap(a[j], a[k]);
}
}
}

1. re 表达式就解决了吧...
2. 所有可能的串做成哈希表, 对匹配串顺序比较 O(n)就可以了吧
3. 匹配 123 4 5 然后做交集然后排除?感觉不如 2 快的样子

bash

echo 123{00..99}56{0..9}8