string - 按前缀对字符串数组进行分组的高效算法

Question

我想知道根据前缀列表(任意长度)对字符串数组进行分组的最佳方法是什么。 例如，如果我们有这个:

prefixes = ['GENERAL', 'COMMON', 'HY-PHE-NATED', 'UNDERSCORED_']

然后

tasks = ['COMMONA', 'COMMONB', 'GENERALA', 'HY-PHE-NATEDA', 'UNDERESCORED_A', 'HY-PHE-NATEDB']

应该这样分组:

[['GENERALA'], ['COMMONA', 'COMMONB'], ['HY-PHE-NATEDA', 'HY-PHE-NATEDB'], ['UNDERESCORED_A'] ]

天真的方法是遍历所有任务并在前缀中进行内部循环(反之亦然)，然后针对每个前缀测试每个任务。

谁能给我一个提示，告诉我如何以更有效的方式做到这一点？

Answer 1

当然，这在一定程度上取决于您的问题的大小，但是如果您对前缀和任务都进行排序，然后通过仅向前遍历两个排序列表来构建子数组，那么您的天真方法应该没问题。