3 ms·
That solution has a complexity problem. It's technically a constant-time overhead (since there's a fixed number of letters in the alphabet, so the complexity is
by zbentley 8y ago
That solution has a complexity problem. It's technically a constant-time overhead (since there's a fixed number of letters in the alphabet, so the complexity is O(26N)->O(N)), but it still seems like an oversight.
'not in alphabetlist' when run on a Python list is an O(N) operation: https://wiki.python.org/moin/TimeComplexity https://wiki.python.org/moin/TimeComplexity. You want a constant-time-search data structure, such as a set or dict.
'alpbabetlist.index(ch)' is another O(N) operation. 'index' searches the whole list.
Additionally (this is a lesser concern), appending to 'letterpos' repeatedly (as in 'letterpos += some_string') can be extremely inefficient on memory. Efficient string concatenation in Python has a number of approaches (http://codingdirectional.info/2018/03/20/return-the-position-of-the-strings-characters-from-the-character-list-with-python/ http://codingdirectional.info/2018/03/20/return-the-position...), but storing a list and concatting its contents together at the end of the function would be a good start.