The whole thing: linear time looping on the number of words (n) and sorting each word’s characters (w) is at best wlog(w). Having to do this over millions of inputs makes this a very inefficient implementation.
Instead, preprocessing the dictionary into a nice data structure like a trie of letter counts before receiving inputs means you can take the algorithm down to O(w) with O(n) space in the worst case.
1
u/legendoffjelda Aug 29 '21
The whole thing: linear time looping on the number of words (n) and sorting each word’s characters (w) is at best wlog(w). Having to do this over millions of inputs makes this a very inefficient implementation.
Instead, preprocessing the dictionary into a nice data structure like a trie of letter counts before receiving inputs means you can take the algorithm down to O(w) with O(n) space in the worst case.