一个这样的字符串 123**56*8,*表示任意数字( 0-9 ),求这个字符串可能的所有子串。
这样的算法该怎么写?
1
qingiqng99 OP 一个这样的字符串 123**56*8,*表示任意数字( 0-9 ),求所有符合要求的字符串。
|
2
zyy314680012 2019-06-05 12:13:43 +08:00 via Android
垃圾算法 n^3
|
3
inhzus 2019-06-05 12:14:52 +08:00 via Android
一个简单的想法,从前往后,遇到数字,就直接继续下一层递归,遇到通配符,就分成 0-9 递归,直到最后一位输出
|
4
pwrliang 2019-06-05 12:20:26 +08:00
你说的是字符串,不是子串吧?把*替换成 0 最小,123005608,替换成 9 最大,123995698。枚举 000-999,填到对应的三个*上不就可以了?
|
5
acehow 2019-06-05 12:26:27 +08:00 via Android
三重循环 0 到 9 呗,这还用啥算法,简直是侮辱算法这个词。
|
6
vibbow 2019-06-05 13:27:41 +08:00
<?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; } |
7
mainjzb 2019-06-05 13:39:27 +08:00
//全排列问题
//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]); } } } |
8
yangyaofei 2019-06-05 14:08:39 +08:00
1. re 表达式就解决了吧...
2. 所有可能的串做成哈希表, 对匹配串顺序比较 O(n)就可以了吧 3. 匹配 123 4 5 然后做交集然后排除?感觉不如 2 快的样子 |
9
goreliu 2019-06-05 14:14:00 +08:00 via Android
bash
echo 123{00..99}56{0..9}8 |