## Identifying Palindromes

### March 31, 2015

It is easy to determine if an array is a palindrome: Start with pointers to the first and last elements of the array. If the two elements are the same, increment the left pointer and decrement the right pointer. Stop with failure if at any point the two elements differ. Stop with success when the two pointers cross:

```(define (palindrome? xv)   (let ((len (vector-length xv)))     (let loop ((left 0) (right (- len 1)))       (cond ((< right left) #t)             ((not (equal? (vector-ref xv left)                           (vector-ref xv right))) #f)             (else (loop (+ left 1) (- right 1)))))))```

```> (palindrome? (vector 1 2 3 4 5 6 7)) #f > (palindrome? (vector 1 2 3 4 3 2 1)) #t```

Determining if a list is a palindrome is harder because the length of the list is now known in advance. We use the tortoise-and-hare algorithm to find the middle of the list, accumulating the elements of the front half of the list while the hare is still in the list and comparing the saved front half of the list to the back half of the list once the hare has reached the end:

```(define (palindrome? xs)   (let loop ((h xs) (t xs) (front (list)))     (cond ((null? t) #t)           ((pair? h)             (if (pair? (cdr h))                 (loop (cddr h) (cdr t)                       (cons (car t) front))                 (loop (cdr h) (cdr t) front)))           ((equal? (car t) (car front))             (loop h (cdr t) (cdr front)))           (else #f))))```

```> (palindrome? (list 1 2 3 4 5 6 7)) #f > (palindrome? (list 1 2 3 4 3 2 1)) #t```

This is clearly O(n), since the tortoise takes one step each time through the loop. The building half of the algorithm occurs in the second `cond` clause, the comparison occurs in the third `cond` clause, and the other two clauses report results. The space complexity is O(n /2), which is the space required to save the front half of the list. If you don’t mind scrambling the list, you could reverse the second half of the list after the hare reaches the end, then compare the front half of the list to the reversed back half of the list, reducing the space complexity to O(1).

You can run the program at http://ideone.com/22EEG0.

Pages: 1 2

### 12 Responses to “Identifying Palindromes”

1. Rutger said

Note that integer division is used, as the middle element of an array of uneven length always satisfies the palindrome condition.

```def is_palindrome(l):
i, max_i = 0, len(l)/2
while i < max_i:
if not l[i] == l[-i-1]:
return False
i+=1
return True

# palindromes
print is_palindrome(list(''))
print is_palindrome(list('1'))
print is_palindrome(list('55'))
print is_palindrome(list('abcba'))
print is_palindrome(list('abccba'))

# not palindromes
print is_palindrome(list('?!'))
print is_palindrome(list('1l'))
print is_palindrome(list('abcbA'))
print is_palindrome(list('abcdba'))

```
2. Paul said
```def is_palindrome(seq):
m = len(seq) // 2
return seq[:m] == seq[:-1-m:-1]

def is_palindrome(seq):
return all(a==b for a, b in zip(seq[:len(seq)//2], reversed(seq)))
```
3. Jussi Piitulainen said

A mindless transcription of the model hare and tortoise to Python:

```def palindromep(xs):
h, t, front	= xs, xs, ()
while True:
if t ==	():
return True
elif h != ():
if h[1] != ():
h, t, front = h[1][1], t[1], (t[0], front)
else:
h, t, front = h[1], t[1], front
elif t[0] == front[0]:
h, t, front	= h, t[1], front[1]
else:
return False

print(palindromep((1,	(2, (3,	(4, (5,	(6, (7, ())))))))))
print(palindromep((1, (2, (3, (4, (3, (2, (1, ())))))))))
```
4. Jussi Piitulainen said

Sorry about the mis-indentations. Something in the copy-and-paste.

5. matthew said

Here’s a list reversing solution, with the list reverse done in place and the correct order restored afterwards:

```#include <stdio.h>
#include <stdlib.h>

struct List {
List(List* next_, int n_) : next(next_), n(n_) {}
List *next;
int n;
};

template <typename T>
void rot3(T &a, T &b, T &c) {
T t = a; a = b; b = c; c = t;
}

void show(List *p) {
printf("[ ");
for ( ; p; p = p->next) {
printf("%d ", p->n);
}
printf("]");
}

bool equal(List *p, List *q)
{
while(p && q) {
if (p->n != q->n) return false;
p = p->next; q = q->next;
}
return p == q;
}

bool check(List *s)
{
List *head = NULL, *tail, *fast = s;
// Scan list, reversing the front part
// Stop when fast pointer gets to end of list
while (true) {
if (!fast) {
// Even sized list
tail = s; break;
}
fast = fast->next;
if (!fast) {
// Odd sized list
tail = s->next; break;
}
fast = fast->next;
}
// Compare head and tail parts
// Now reverse back again
return res;
}

int main(int argc, char *argv[])
{
List *s = NULL;
for (int i = 1; i < argc; i++) {
s = new List(s,strtol(argv[argc-i],NULL,0));
}
bool res = check(s);
show(s);
printf(": %s\n", res ? "Palindrome" : "Not a palindrome");
}
```
6. Krishnan R said

Palindrome Check for Arrays:

```public class PalindromeCheckArray {

public static void main(String[] args) {
boolean test;
char[] input1 = new char[] {'h','e','l','l','o'};
test = isPalindrome(input1);
System.out.println(test);

char[] input2 = new char[] {'r','e','p','a','p','e','r'};
test = isPalindrome(input2);
System.out.println(test);
}

private static boolean isPalindrome(char[] input) {
int i,j;
for(i=0,j=input.length-1;i<j;i++,j--) {
if(input[i] != input[j]) {
return false;
}
}
return true;
}
}
```
7. Sumesh Balan said

import java.util.List;
import java.util.Scanner;

public class ListPalidrome {
private static List myList;

public static void main(String[] args) {
System.out.println(“enter the elements in list, enter e to stop”);
Scanner sc = new Scanner(System.in);

while (sc.hasNextInt()) {
}

sc.close();
System.out.println(isPalidrome(myList));
}

private static boolean isPalidrome(List myList) {
// input is empty or single element, return true
if (myList.isEmpty() || myList.size() == 1) {
return true;
}

// use an aux list for storing first half of the list

int len = myList.size();
int t = 0;// tortoise
int h = 0;// hare

while (h < len – 1) {
// add tortoise to front of auxList
t++;
// double increment hare
h += 2;
}

//if length is odd, skip the middle element from comparison
if(len % 2 != 0) t++;

//compare tortoise journey to auxList
int k = 0;
while (t < len) {
if (myList.get(t++) != auxList.get(k++))
return false;
}
return true;
}
}
Code Formatted by ToGoTutor

8. Krishnan R said
```
class Node {

Node next;
Object data;

public Node(Object dataValue) {
next = null;
data = dataValue;
}
}

class PalindromeList {

public PalindromeList() {

}
public PalindromeList(String nodeData) {
}

Node temp = new Node(data);
while (current.next != null)
current = current.next;

current.next = temp;
}

while(current.next != null)
current = current.next;

for(int i=1;i<dataArr.length;i++) {
Node temp = new Node(dataArr[i]);
current.next = temp;
current = current.next;
}
}
}

public class PalindromeTest {
public static void main(String[] args) {
PalindromeList pList = new PalindromeList();
String[] inputData = new String[] {"1","2","3","4","5","6"};
test(pList);

PalindromeList pList1 = new PalindromeList();
String[] inputData1 = new String[] {"1","2","3","1","2","3"};
test(pList1);

PalindromeList pList2 = new PalindromeList();
String[] inputData2 = new String[] {"1","1","1","1","1","1"};
test(pList2);

PalindromeList pList3 = new PalindromeList();
String[] inputData3 = new String[] {"1"};
test(pList3);
}

private static void test(PalindromeList pList) {
PalindromeList tortoise = pList;
PalindromeList hare = pList;

boolean lame_flag = false;

while(true) {
if(hNode.next == null) {
tNode = tNode.next;
break;
} else if(hNode.next.next == null) {
fNode.next = new Node(tNode.data.toString());;
tNode = tNode.next;
break;
} else {
if(lame_flag) {
fNode.next = new Node(tNode.data.toString());
fNode = fNode.next;
}
lame_flag = true;
tNode = tNode.next;
hNode = hNode.next.next;
}
}

//Now that hare and tortoise are ready, check if palindrome;
while(true) {
if(tNode == null)
break;
if(tNode.data.toString().equals(fNode.data.toString())) {
tNode = tNode.next;
fNode = fNode.next;
}
else {
System.out.println("Not a palindrome");
return;
}
}
System.out.println("It's a palindrome!");
}

//Not called anywhere, still..
private static void printPalindrome(Node node, String name) {
System.out.println("Printing "+name);
while(node != null) {
System.out.println(node.data.toString());
node = node.next;
}
System.out.println("*******************************");
}
}
```
9. […] of my favorite sites Programming Praxis recently had an entry on detecting palindromes. Even if you’re not interested in palindromes, […]

10. Sanjay said

import sys

def check_palindrom(input_list):
if len(input_list) == 1:
return “YES, A Palindrom”
else:
mid = len(input_list)/2
print “MID=”, mid
for i in range(mid):
if (input_list[i] != input_list[len(input_list)-1-i]):
return “No, Not a Palindrom”
else:
continue
return “YES, A Palindrom”

print “Enter the array element with space seperated. Press Enter when done”
input_array = raw_input()
input_list = input_array.split()
print len(input_list)
input_list = [sys.exit(1) if len(input_list)< 1 else (j) for j in input_list]
print input_list
print check_palindrom(input_list

11. fisherro said

A C++ version that works with std::vector, std::list or any class that supports begin, end, rbegin, and rend. (Since std::list is doubly-linked, it makes things easier.)

```template<typename C>
bool is_palindrome(const C& c)
{
auto forwards = c.begin();
auto end = c.end();
auto backwards = c.rbegin();
auto rend = c.rend();
while (true) {
if (end == forwards) return false; //paranoia
if (rend == backwards) return false; //paranoia
if (*forwards != *backwards) return false;
++forwards;
if (forwards == backwards.base()) break;
++backwards;
if (forwards == backwards.base()) break;
}
return true;
}
```
12. fisherro said

This version uses std::mismatch. In essence this is similar to the previous version I posted, except we have to precalculate the end condition using c.size and std::advance. Not a big deal for std::vector, but not good for std::list. Some implementations of std::list maintain a size member variable making c.size O(1) instead of O(n), so the impact varies.

```template<typename C>
bool is_palindrome(const C& c)
{
auto last = c.begin();