查找多个常见的起始字符串

Question

我有一个字符串列表,其中一个或多个字符串子集有一个共同的起始字符串.我想要一个函数,它将原始字符串列表作为输入,并返回所有常见起始字符串的列表.在我的特定情况下,我也知道每个公共前缀必须以给定的分隔符结束.下面是我正在谈论的输入数据类型的示例(忽略任何颜色突出显示):

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

这里的分隔符是/和常见的起始字符串是Population of metro area和Population of city.也许这个分隔符最终不会重要,但我已经把它强调我不希望只有一个结果回来,即普遍的共同起始字符串Population of; 我也不想要共同的子串Population of metro area / S和Population of city / S.

此算法的最终用途是按字母顺序对字符串进行分组.例如,上面的列表可以重新构建为一个消除冗余信息的层次结构,如下所示:

Population of metro area
    Portland
    San Francisco
    Seattle
Population of city
    Portland
    San Francisco
    Seattle

我正在使用Python,但任何语言的伪代码都可以.

编辑 正如Tom Anderson所指出的那样,给出的原始问题很容易简化为简单地拆分字符串并使用哈希按前缀分组.我原本以为问题可能会更复杂,因为有时在实践中我会遇到带有嵌入分隔符的前缀,但我意识到这也可以通过简单地做一个仅限于拆分一次的正确拆分来解决.

Answer 1

这不仅仅是在字符串上循环,将它们分隔在分隔符上,然后将前半部分分成两半吗？像这样:

def groupByPrefix(strings):
    stringsByPrefix = {}
    for string in strings:
            prefix, suffix = map(str.strip, string.split("/", 1))
            group = stringsByPrefix.setdefault(prefix, [])
            group.append(suffix)
    return stringsByPrefix

一般来说,如果你正在寻找字符串前缀,那么解决方案就是将字符串转换为trie.具有多个子节点的任何分支节点都是最大公共前缀.但是你的需求比这更受限制.

Answer 2

d = collections.defaultdict(list)

for place, name in ((i.strip() for i in line.split('/'))
                    for line in text.splitlines()):
    d[place].append(name)

所以d将是一个像这样的词典:

{'Population of city':
       ['Portland',
        'San Francisco',
        'Seattle'],
 'Population of metro area':
       ['Portland',
        'San Francisco',
        'Seattle']}

如果您知道文本周围没有额外的空格(i.strip() for i in line.split('/'),line.split(' / ')则可以替换.