Why is this algorithm
S = S.replace('-','').upper() i = len(S)%K if len(S)%K else K ans = S[:i] while i <= len(S)-K: ans += '-' + S[i:i+K] i += K return ans
rev = '' curr = '' S = S.strip('-') for i in xrange(len(S)): if S[~i] != '-': curr += char.upper() if len(curr) == K: rev += curr if i != len(S)-1: rev += '-' curr = '' if curr: rev += curr return rev[::-1]
The first one does two operations to the entire string at the very beginning and then iterates through it again. I would think that this would be slower than the second algorithm, which really only iterates through the string once (granted I'm not sure what the time complexity of reversing a string for the return would be). Why is the first one so much faster (about 1/3 the running time)? Is it because
upper are written in native C?
Yes you are right, replace are upper are so much faster because they are written in C. Condition statements and compare operators are much slower in Python.
Also, you might notice that your second algorithm also go through the whole string one extra time when reversing it in the end.
Yes I thought that the
[::-1] might also be O(n) but that it would at least be a very fast iteration as it did nothing to each element. In any case, the key is that replace and upper are written in C. Thanks.