- An empty string is a palindrome.
- A string with one character is a palindrome.
- If a string starts and ends with the same character, and the substring between them is a palindrome, then the entire string is a palindrome.
I wrote them the iterative version so I wouldn't look like an idiot. The iterative version is generally faster with a standard compiler, but it is more complex. Not much more complex, but still, you have to keep track of two indexes into the string and how close they've gotten to each other.
The recursive solution is just more elegant.
Apparently I cannot post comments on my own blog. Well, I can edit the post. "if s[pos] != s[-pos-1]" sure looks like two pointers, but to be fair, the recursive solution hides its pointers in the string structure or in the slices if it is using them. As for "(string= x (string-reverse x))", there is something elegant in something that crude.
3 comments:
Why do you need to keep track of two indices in the iterative solution?
def palindrome(s):
for pos in range((len(s) + 1) // 2):
if s[pos] != s[-pos-1]:
return False
return True
(which is just all(s[pos] == s[-pos-1] for pos in range((len(s) + 1) // 2)))
(How do you post code in Blogger comments?)
alternative formulation:
(string= x (string-reverse x))
Elegant for blog posting does not mean you don't want the imperative version in production code :)
It's very probably faster in optimized builds, so much faster in unoptimized builds, doesn't need allocations, and not that much harder.
It factors in elegance for me, terseness is not the alpha and omega :)
Post a Comment