Re:Can you solve it? The Greplin programming challenge
by l0nwlf on Friday October 08, 2010 @03:25PM
(#1772996)
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.
[ Parent
| on HN ]
Re:Can you solve it? The Greplin programming challenge
by orangecat on Friday October 08, 2010 @04:38PM
(#1773279)
Isn'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.
Re:Can you solve it? The Greplin programming challenge
by brown9-2 on Friday October 08, 2010 @04:49PM
(#1773323)
reverse substring and compare
D'oh! My is_palindrome(word) just got a lot shorter, thanks :)
Re:Can you solve it? The Greplin programming challenge
by johnfn on Friday October 08, 2010 @07:44PM
(#1773880)
3-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! :)