这是其中一个问题,在任何高级语言中都是小菜一碟,但在用纯 C 编写代码时,我不知道该怎么做才能不让我的代码变得一团糟:
我有一个由独特字母组成的字母表,以及一个带有一些数字的字符串,例如“test01test21”。我需要生成用字母替换数字所产生的所有字符串(因此每个数字 0,1,2,... 都得到它的字母(不一定是唯一的),我们需要遍历所有可能的字母数字替换,以便生成所有字符串),并以某种方式返回这些字符串。
问题看似简单,但越想越难。在返回结果时,我已经对动态字符串列表结构进行了编码,因此这不是主要问题。我想知道的是如何遍历所有字母数字替换(请记住,数字集不是常数,一个字符串中要替换的数字可能是 {0,1,2} 而另一个 { 3,7,9},但它始终是一些数字集),以下是我考虑过的几种实现方法:
- 我们可以创建 10 个嵌套的 for 循环,循环遍历字母表以替换 10 个可能的数字中的每一个。这个问题 - 它是高度不可编码的,并且做了太多不必要的计算。
- 我们可以在一开始就创建一个包含 10 个元素的伪初始化数组,扫描整个字符串,标记所有出现的数字,将它们复制到另一个数组。现在初始数组将用作数字字母映射,第二个数组(数字集)将以某种方式为我们提供“迭代器助手”(我们必须以某种方式迭代第 1 点中的数字,只是这次会有是 |number-set| 嵌套 for 循环而不是 10 个 for 循环)。这方面的问题——我仍然不知道如何通过数字集对迭代进行编码,正如你所看到的,即使在文本中它也会很快变得复杂——我不想考虑如果我是会发生什么用 C 编写代码。
我真的想不出别的了。我认为这两种方式都有缺陷,会导致代码非常复杂。问题是——当你必须用 C 语言解决这类问题时怎么办?如果有任何提示可以帮助我编写代码并以某种方式组织代码,我将不胜感激...
示例输出:
字母“ab”
字符串“ab01”
输出 {"abaa","abab","abba","abbb"}
最佳答案
你必须使用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
关于C - 高效编码字符串生成算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30682772/