C - 高效编码字符串生成算法

Question

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

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

问题看似简单，但越想越难。在返回结果时，我已经对动态字符串列表结构进行了编码，因此这不是主要问题。我想知道的是如何遍历所有字母数字替换(请记住，数字集不是常数，一个字符串中要替换的数字可能是 {0,1,2} 而另一个 { 3,7,9}，但它始终是一些数字集)，以下是我考虑过的几种实现方法:

1. 我们可以创建 10 个嵌套的 for 循环，循环遍历字母表以替换 10 个可能的数字中的每一个。这个问题 - 它是高度不可编码的，并且做了太多不必要的计算。
2. 我们可以在一开始就创建一个包含 10 个元素的伪初始化数组，扫描整个字符串，标记所有出现的数字，将它们复制到另一个数组。现在初始数组将用作数字字母映射，第二个数组(数字集)将以某种方式为我们提供“迭代器助手”(我们必须以某种方式迭代第 1 点中的数字，只是这次会有是 |number-set| 嵌套 for 循环而不是 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