Linked List Palindrome
September 8, 2017
Our solution appends all the list items into a single string, splits the string into a list of characters, then compares the list to its reverse (we could do without the intermediate list if Scheme had a string-reverse
):
(define (palindrome? strs) (let ((cs (string->list (apply string-append strs)))) (equal? cs (reverse cs))))
Here are two examples:
> (palindrome? '("a" "bcd" "ef" "g" "f" "ed" "c" "ba")) #t > (palindrome? '("a" "bcd" "ef" "g" "f" "ed" "ba")) #f
You can run the program at https://ideone.com/UIP1Ml.
You should look at the sixty-six posted solutions on the original problem page. It is astonishing to me that so many programming languages take a simple problem and make it extraordinarily complex. Well, at least the code to solve the problem is complex. Maybe it’s the programmers and not the programming languages that cause the complexity? In any event, some of those solutions are absolutely beyond belief. You will either laugh or cry, or both.
The following should run in time linear in the input size, and is a
bit more general than needed.
I was asked a palindrome question yesterday, but it explicitly excluded any solution that involved reversing or flattening, as it had to execute in O(1) space.
Note: it is possible to make it O(1) in space, but this will degrade into O(e^2)+O(n) instead of O(e)+O(n) in time since we will have to traverse the list several time, by index. (with e = (length list) and n = total number of characters). It will also be O(t^2) in programmer time, with t being the time the programmer took to implement the second version above… ;-)
Prompted by John Cowan’s comment above, here is a version that is
constant space, but quadratic time.
If using SRFI-135 is considered “cheating” then we could impagine we
have included code from portable implementation from that SRFI. (We
could also use “istrings” from SRFI 140 or Kawa, etc.)