Fastest theoretical solution for IsIsogram(): My vote is for O(n) - here's how

This is one from my son James:

I think that the best way of doing this is in fact using a Radix Sort, which has been calculated to O(wn). The sort works by going through each element and assigning each character a predesignated spot in a lookup table. The sorting method never makes any comparisons, but in stead goes sequentially through the lookup table in ascending order to sort the original inputs. See also To make the process more efficient I would just make an array of integers as my lookup table, and then I would only need to worry about incrementing one of 26 numbers per character in the word. This would also make the whole method easier to write and perform since once any number in the lookup array increments past 1, then I can safely say that there is a repeating letter. Thus it further reduces to O(n).


Privacy & Terms