I don't think your code is correct. You are only removing the items that are equal to some prefix of the currently processed $word. You should delete all substrings, not only the prefixes. That would make your solution O(N*log N + N*M*M). We don't know the expected N and M, but this makes the M much more important.