3 ms·
It depends how you count. Is string reversion an O(1) or O(N) operation with N the string length? I believe is is O(N) and if you loop over it N times thats O(N
by andi999 6y ago
It depends how you count. Is string reversion an O(1) or O(N) operation with N the string length? I believe is is O(N) and if you loop over it N times thats O(N^2), isnt it?
- im3w1l 6y agoI didn't want to post code, but I guess it's the only way I can see to settle the debate. This should be manifestly linear. def check(s): is_palindrome = lambda s: s == s[::-1] if is_palindrome(s): return True d = [a==b for a, b in zip(s, s[::-1])].index(False) return is_palindrome(s[d+1:len(s)-d]) or is_palindrome(s[d:-d-1]) edit: It must be len(s)-d rather than -d, to handle d=0.