java - 查找按字符索引分组的多个字符串并集的算法

Question

我一直在尝试寻找一种高效的方法来查找一组按索引分组的 fixed width 字符出现的并集。像这样的东西；

s1 = "013965"
s2 = "015935"
s3 = "310012"

结果如下，其中每组数字都存在于字符索引 n 处的所有字符串中:

out = "[03][1][350][90][631][52]"

我曾想过用一种非常天真的方法来遍历每个字符串，在每个索引处，同时将中间字符串存储在一个数组中，然后遍历该数组以构建输出值。然而，我的方法在我看来是一种非常低效的方式，与渐近最优解决方案相去甚远。

Answer 1

如果事先知道所有可能字符的集合，假设它们的编号是 n，n 不会太高(例如 10，如果您只做数字)，你可以通过创建长度为 n 的 m boolean 数组来做到这一点，其中 m 是位置的数量，或者是数字输入字符串和 n。如果第 n 个字符出现在任何输入字符串的第 m 个位置，则第 m 个数组中的第 n 个位置将为 true。 False 表示之前没有这样的字符出现在第 m 个位置。

然后你可以遍历每个字符串，当你在 m 位置遇到字符 n 时，你在第 n 个位置标记 true第 m 个数组。最后，您将有 m 数组，每个数组描述第 m 组的内容

pos[0] = {true, true, false, false, false, true, true, false, true, false}
pos[1] = {true, false, false, false, false, false, false, false, false, false}
pos[2] = {false, false, true, true, false, false, false, false, false, true}

翻译成

[0,1,5,6,8] [0] [2,3,9]

由于所有结构都是直接访问数组，不涉及查找，所有访问都在常数时间内，您只需访问每个字符一次，不涉及比较。希望这会有所帮助。