V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
qingiqng99
V2EX  ›  算法

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

  •  
  •   qingiqng99 · 2019-06-05 12:04:51 +08:00 · 2929 次点击
    这是一个创建于 1988 天前的主题,其中的信息可能已经有所发展或是发生改变。

    一个这样的字符串 123**56*8,*表示任意数字( 0-9 ),求这个字符串可能的所有子串。

    这样的算法该怎么写?

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

    echo 123{00..99}56{0..9}8
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5695 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 18ms · UTC 03:29 · PVG 11:29 · LAX 19:29 · JFK 22:29
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.