Optimizing time complexity of prefix searching between two lists

Looking to refactor some legacy code, and I have a method that's functionally similar to the following simplified version:

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;
}

I was looking for ways to increase the speed of the method, and came across Tries in another stack overflow post somewhere. After doing some research, though they were cool so I reimplemented the method as following:

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());
}

The method is much simpler to look at in my opinion, and that's a plus already for me but I'm second guessing that it's time complexity improvement. My first instinct is that it's gone from O(n^2) to O(n). After all the second method is taking O(n) to load the trie, O(m) to search prefixes with O(n)lookup thanks to the trie (from the the apache docs).

But in the second stream, I'm doing an O(n) lookup O(m) times, so I'm hitting O(n^2) anyway, correct? Is there a more efficient or intelligent way to perform this style of operation?