C/C++, Codes

Checking for PalinDrome.

A palindrome is any word, phrase, number that is the same either backwards or forwards.

A couple example :

A but tuba.
A car, a man, a maraca.
A dog, a plan, a canal: pagoda.
A dog! A panic in a pagoda!

Let’s look at the general requirement of a palindrome at first:

1. A string with one length, in other word, a character is not considered a Palindrome.(This can be accomplish by using another function that check for goodStr before checking Palindrome.)
2. Forward and backwards corresponding characters are the same.

bool goodStr(string s)
{
	//a char or empty string is
	//not acceptable.
	if (s.length()
		return false;
        //everything fine here.
	return true;
}

There are two ways to program the problem at least(2 ways I can think of^^) : Recursion and Iteration.

a.Recursion

The Idea of Recursion is simple. You pass the string into the function and check for first and last character of the string.

If they are equal, continue calling the same function, except passing the new ‘first-and-last-character-cutoff’ string. The base case/ ending condition would be when the string is empty when you cut all the character out.

If during the recursion, the two compared characters is not equaled, just return false, and get back to main.

bool recurPalinDrome(string s)
{
	//base case
	if (s.length() == 0)
		return true;

	//make sure the two comparing characters is ALWAYS lowercase
	if ((tolower(s[0])) == (tolower(s[s.length()-1])))
		return recurPalinDrome(s.substr(1,s.length()-2));

	//fall out
	return false;
}

b.Iteration
Iteration is more intuitive than recursion – it is the thought flow of the program.
Basically you loop from two ends : first character forward and last character backward, and compare during the run. If equal, continue; otherwise, get out of the loop.

        int st = 0, end = s.length()-1;
	int i = 0;

	//loop from two ends
	while ((s[st] == s[end])
			&& (i < s.length()/2))
	{
			st++;
			end--;
			i++;
	}

Condition for checking complete loop and incomplete loop. It would get out of the loop block whenever one of the comparison is false, or it gets to the middle of the string. Well, respectively, it is not a Palindrome, it is a Palindrome. Check this out:

//loop ends whenever
//it reach the middle of the string

if (i == s.length()/2)
	return true;

//or one of the comparison fails
else return false;

Bum! That is the whole thing.

This is the full code .

/**
  @author : Ho Duc.
  @Goal   : Checking Palindrome of the string.
  @Lang   : C++.
  @Date   : 02/24/2012.
 *

#include <iostream>
#include <string>
using namespace std;

bool goodStr(string s)
{
	//a char or empty string is
	//not acceptable.
	if (s.length() <= 1)
		return false;
	//everything fine here
	return true;
}
bool recurPalinDrome(string s)
{
	cout << s << endl;
	//base case
	if (s.length() == 0)
		return true;
	//make sure the two comparing characters is ALWAYS lowercase
	if ((tolower(s[0])) == (tolower(s[s.length()-1])))
		return recurPalinDrome(s.substr(1,s.length()-2));

	//fall out
	return false;
}

bool itePalinDrome(string s)
{
	int st = 0, end = s.length()-1;
	int i = 0;

	//loop from two ends
	while ((s[st] == s[end])
			&& (i < s.length()/2))
	{
			st++;
			end--;
			i++;
	}

	//loop ends whenever
	//it reach the middle of the string
	if (i == s.length()/2)
		return true;
	//or one of the comparison fails
	else return false;
}
int main()
{
	string s;
	cout << "Enter a string :";
	cin  >> s;
	if (goodStr(s) == true)
	{
		if(recurPalinDrome(s) == true)
 		//if(itePalinDrome(s) == true)
			cout << "YES";
		else cout << "NO";
	}
	else cout << "NO";
	return 0;
}

Sample run :

Enter a string: racecar
YES.

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