优化两个列表之间的前缀搜索的时间复杂性

Question

希望重构一些旧代码，并且我有一种与以下简化版本相似的方法：

public static List<String> getAllPrefixedCodes(List<String> codes, List<String> prefixes) {
   var prefixedCodes = new ArrayList<String>();
   for (String code : codes) {
      for (String prefix : prefixes) {
         if (code.startsWith(prefix)) {
            prefixedCodes.add(code);
         }
      }
   }

   return prefixedCodes;
}

我正在寻找提高方法速度的方法，并在其他堆栈溢出帖子中进行了尝试。经过一些研究后，尽管它们很酷，所以我重新完成了该方法如下：

public static List<String> getAllPrefixedCodes(Collection<String> codes, Collection<String> prefixes) {
   final var trie = codes.stream()
                    .collect(Collectors.toMap(Function.identity(), Function.identity(), 
                       (a, b) -> a, PatriciaTrie::new));

   return prefixes.parallelStream()
             .map(trie::prefixMap)
             .map(SortedMap::values)
             .flatMap(Collection::stream)
             .collect(Collectors.toList());
}

我认为该方法更简单，这对我来说已经是一个加号，但是我第二次猜测这是时间复杂性的改善。我的第一个本能是它已经从o（n^2）变成了o（n）。在所有第二种方法都将O（n）加载到Trie之后，o（m）通过Trie搜索O（n）查找的前缀（来自）。

但是在第二个流中，我正在做一个O（n）查找o（m）次，所以无论如何我都击中o（n^2），对吗？是否有一种更有效或更聪明的方法来执行这种操作风格？