Identifying Palindromes

March 31, 2015

Today’s task sounds simple but leads to a little bit of complexity.

Given an array, determine if it is a palindrome. Given a linked list, determine if it is a palindrome. Make both tests as efficient, in both time and space, as possible.

Your task is to write two programs to identify palindromes. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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;
        rot3(head,s,s->next);
      }
      // Compare head and tail parts
      bool res = equal(head,tail); 
      // Now reverse back again
      while (head) rot3(s,head,head->next);
      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.LinkedList;
    import java.util.List;
    import java.util.Scanner;

    public class ListPalidrome {
        private static List myList;

        public static void main(String[] args) {
            myList = new LinkedList();
            System.out.println(“enter the elements in list, enter e to stop”);
            Scanner sc = new Scanner(System.in);
            
            while (sc.hasNextInt()) {
                myList.add(sc.nextInt());
            }
            
            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
            List auxList = new LinkedList();
            
            int len = myList.size();
            int t = 0;// tortoise
            int h = 0;// hare

            while (h < len – 1) {
                // add tortoise to front of auxList
                auxList.add(0, myList.get(t));
                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 Node head;
    
    	public PalindromeList() {
    		
    	}
    	public PalindromeList(String nodeData) {
    		head = new Node(nodeData);
    	}
    
    	public void add(Object data) {
    		Node temp = new Node(data);
    		Node current = head;
    		while (current.next != null)
    			current = current.next;
    
    		current.next = temp;
    	}
    	
    	public void addAll(Object[] dataArr) {
    		head = new Node(dataArr[0]);
    		
    		Node current = head;
    		
    		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"};
    		pList.addAll(inputData);
    		test(pList);
    		
    		PalindromeList pList1 = new PalindromeList();
    		String[] inputData1 = new String[] {"1","2","3","1","2","3"};
    		pList1.addAll(inputData1);
    		test(pList1);
    		
    		PalindromeList pList2 = new PalindromeList();
    		String[] inputData2 = new String[] {"1","1","1","1","1","1"};
    		pList2.addAll(inputData2);
    		test(pList2);
    		
    		PalindromeList pList3 = new PalindromeList();
    		String[] inputData3 = new String[] {"1"};
    		pList3.addAll(inputData3);
    		test(pList3);
    	}
    	
    	private static void test(PalindromeList pList) {
    		PalindromeList tortoise = pList;
    		PalindromeList hare = pList;
    		PalindromeList front = new PalindromeList(tortoise.head.data.toString());
    		
    		Node tNode = tortoise.head;
    		Node hNode = hare.head;
    		Node fNode = front.head;
    		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;
    			}
    		}
    		fNode = front.head;
    		
    		//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();
        std::advance(last, c.size() / 2);
        auto result = std::mismatch(c.begin(), last, c.rbegin());
        return result.first == last;
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: