C - 编码串生成算法

Question

这是其中一个问题,在任何更高级别的语言中都是小菜一碟,但是当用纯C语言编写它时,我不知道该怎么做才能不把我的代码变成一团糟:

我有一个独特字母的字母表,以及一些带有一些数字的字符串,例如"test01test21".我需要生成所有字符串,这些字符串是用字母替换数字(所以每个数字0,1,2,...得到它的字母(不一定是唯一的),我们需要遍历所有可能的字母数字替换,以便生成所有字符串),并以某种方式返回这些字符串.

问题似乎很容易,但我想的越多,问题就越多.当返回结果时,我已经编码了动态字符串列表结构,因此它不是主要问题.我想知道的是如何遍历所有字母数字替换(请记住,数字集不是常数,要在一个字符串中替换的数字可能是{0,1,2}而在另一个字符串中{例如,3,7,9},但它总是一些数字集合,这里有几种方法我做过这样的思考:

1. 我们可以制作10个嵌套for循环,迭代10个可能的数字中的每一个来替换.这个问题 - 它是高度无法编码的,并且做了太多不必要的计算.
2. 我们可以在最开始做出10个元素的假初始化数组,扫描字符串,标记所有当前数字,将它们复制到其他数组.现在,初始数组将用作数字字母映射,第二个数组(数字集)将以某种方式为我们提供"迭代器帮助器"(我们必须以某种方式遍历数字,如第1点所示,只有这次会有be | number-set |嵌套for-loops而不是10 for循环).这个问题 - 我仍然不知道如何通过数字集编码迭代,你可以看到它甚至在文本中很快变得复杂 - 我不想想如果我是什么会发生什么用C编写代码

我真的想不出别的什么.我认为这两种方式都存在缺陷,导致代码非常复杂.问题是 - 当你必须在C中解决这类问题时该怎么办？我会感谢任何有助于我编写代码并以某种方式组织代码的提示......

样本输出:

字母"ab"

字符串"ab01"

输出{"abaa","abab","abba","abbb"}

Answer 1

您必须使用tries数据结构.刚开始阅读你的字符串并构建tries.让我们举个例子,它应该是这样的.

    a             a
    |             |
    b             b
    |            / \
    0    -->    a   b
    |          / \ /  \
    1         a   b    a
              |   |    |
             \0  \0   \0

上面例子中按字符构建的字符:

a ------ b -------  0 -------  1 ------- \0

a ---->  a ------>  a ------>  a ------>   a 
|        |          |          |           |
\0      >b          b          b           b
         |         / \        / \         / \
        \0      >a    b      a   >b      a   b
                 |    |     / \   |     / \ / \
                \0   \0    a   b  \0   a   b   a
                          |   |        |   |   |
                         \0   \0       \0  \0  \0

                              |
                              |
                              v

                              a
                              |
                              b
                            /  \
                           a    b
                          / \  / \
                         a    b   a 
                         |    |   |  
                        \0   \0  \0

现在你所要做的就是遍历尝试.请查看这些有用的链接以获取帮助:1 2