4 ms·
Brute works here because of bad test case. Author could have generated a smart test case and then optimal algorithm could be using suffix array which takes O(n)
by l0nwlf 16y ago
Brute works here because of bad test case. Author could have generated a smart test case and then optimal algorithm could be using suffix array which takes O(n), brute would take O(n!). However a bit smart brute gave the answer in approx 3-4 minutes ( computation + coding time). And yes, Python FTW.
- orangecat 16y agoIsn't brute force just O(n^3)? Loop over each character to start potential palindrome, loop from start character to end, reverse substring and compare. But yeah, the test input should be longer and/or smarter. Ditto on the third problem.
- brown9-2 16y agoreverse substring and compare D'oh! My is_palindrome(word) just got a lot shorter, thanks :)
- preek 16y ago3-4min? Since it was only like 5 lines of code I did it in brute force. Python and Mac Mini here - the answer came almost instantaneously.
- l0nwlf 16y agoBy 3-4 minutes I mean both computation as well as coding time. Solution of mine came in < 1s.
- johnfn 16y ago3-4 minutes! Try this: for i in range(len(str)): for j in range(i, len(str)): if str[i:j] == str[i:j][::-1]: #... Choose the start and end indices. Then take a slice to see if it's a palindrome. Nice and speedy! :)