Sunday 27 May 2012

Interviewstreet CouponDunia Palindrome Problem


Interviewstreet CouponDunia Palindrome Problem


Problem Statement

Given a string, determine whether it is palindrome or not. Output 1 for palindrome, and output 0 for not a palindrome.

A palindrome is a string that when reversed is equivalent to its original. Assume case is insensitive and then all non letters are ignored in calculating whether the string is palindrome.

Sample Input:
Dad
Sample Output:
1

Sample Input:
A man, a plan, a canal - Panama!
Sample Output:
1


Solution
 
#include<iostream>

#define MAX 1000
using namespace std;


int main()
{
 char s[MAX];
 cin>>s;
 int n=strlen(s);

 int i=0,j=n-1;
    while(i<j)
    {

              if(tolower(s[i])!=tolower(s[j]))
              break;
              i++;
              while(tolower(s[i])==s[i]&&(toupper(s[i])==s[i]))
              i++;
              j--;
              while((tolower(s[j])==s[j])&&(toupper(s[j])==s[j]))
              j--;

    }
    if(i>=j)
    cout<<1;
    else
    cout<<0;

}

Time Complexity: O(n)

4 comments:

  1. Nice CouponDunia Palindrome coding.....



    CouponAMMU

    ReplyDelete
  2. public static int main(String s)
    {
    char a,b;
    for(int i=0,j=s.length()-1; i<j;)
    {
    a = Character.toLowerCase(s.charAt(i));
    b = Character.toLowerCase(s.charAt(j));
    if(!Character.isLetter(a))
    {
    i++;
    continue;
    }
    if(!Character.isLetter(b))
    {
    j--;
    continue;
    }
    if(a == b)
    {
    i++;
    j--;
    }
    else
    return 0;
    }
    return 1;
    }

    ReplyDelete
  3. import java.util.*;
    import java.lang.*;
    import java.io.*;

    /* Name of the class has to be "Main" only if the class is public. */
    class Ideone
    {
    public static void main (String[] args) throws java.lang.Exception
    {
    // your code goes here
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    String s=br.readLine();
    int val=0;
    char arr[]=s.toCharArray();

    int a=arr.length;
    a--;
    int b=0;

    while(a>b)
    {
    if(arr[a]<65 ||(arr[a]>90 && arr[a]<97) || arr[a]>122)
    {
    a--;
    continue;
    }
    if(arr[b]<65 ||(arr[b]>90 && arr[b]<97) || arr[b]>122)
    {
    b++;
    continue;
    }
    char t1=Character.toLowerCase(arr[a]);
    char t2=Character.toLowerCase(arr[b]);
    if(t1!=t2)
    {
    val=1;
    break;
    }

    a--;
    b++;
    }
    if(val==1) System.out.println("0");
    else System.out.println("1");
    }

    }

    ReplyDelete