我有一列字符串,其中一个或多个子字符串具有共同的起始字符串。我希望有一个函数,可以将原始的字符串列表作为输入,并返回所有共同起始字符串的列表。在我的情况下,我还知道每个共同前缀必须以给定的分隔符结尾。以下是我所说的输入数据类型的示例(忽略任何颜色突出显示):
该算法的最终使用目的是按照它们的公共前缀将字符串分组。例如,上面的列表可以重新结构化成一个层次结构,消除冗余信息,如下所示:
编辑 正如Tom Anderson所指出的那样,原始问题可以轻松地简化为仅仅是将字符串拆分并使用哈希来按前缀分组。我最初认为这个问题可能更加复杂,因为在实践中有时会遇到具有嵌入式分隔符的前缀,但我意识到这也可以通过仅对一个右拆分进行限制来解决。
这里的分隔符是Population of metro area / Portland Population of city / Portland Population of metro area / San Francisco Population of city / San Francisco Population of metro area / Seattle Population of city / Seattle
/
,常见的起始字符串是都市区人口
和城市人口
。也许分隔符并不重要,但我想强调的是,我不希望只返回一个结果,即普遍通用的起始字符串人口
;我也不希望返回常见子字符串都市区人口 / S
和城市人口 / S
。该算法的最终使用目的是按照它们的公共前缀将字符串分组。例如,上面的列表可以重新结构化成一个层次结构,消除冗余信息,如下所示:
Population of metro area
Portland
San Francisco
Seattle
Population of city
Portland
San Francisco
Seattle
我正在使用Python,但任何语言的伪代码都可以。编辑 正如Tom Anderson所指出的那样,原始问题可以轻松地简化为仅仅是将字符串拆分并使用哈希来按前缀分组。我最初认为这个问题可能更加复杂,因为在实践中有时会遇到具有嵌入式分隔符的前缀,但我意识到这也可以通过仅对一个右拆分进行限制来解决。