Palindrome problem

Problem

The palindrome problem is another classic algorithm question.

Given the sentence, write the code checking if the sentence is a palindrome. Any non-alphabet characters should be ignored.

Examples:

A car, a man, a maraca.
A dog, a plan, a canal: pagoda.
A dog! A panic in a pagoda!
A lad named E. Mandala
A man, a plan, a canal: Panama.

Answer

The algorithm should ignore all but the alphabet. The expected running time is O(N).
This algorithm is quite straightforward.

We can set two pointers: start, and end. start pointer begins with the 0th position and the end pointer starts with $N-1$th position.

Each time we compare the characters pointed by these two points. If they don't match, it is not a palindrome.

If they do, increment a start pointer by 1 and decrement an end pointer by 1 and perform the comparison.

Repeat this process until start >= end.

If you have questions, feel free to add them to the comments.

Here is the code

	#include <iostream>
	#include <string>
	#include <math.h>
	using namespace std;
	bool IsAlphabet(char c)
	{
	return ((c >='a' && c<='z')||(c>='A' &&c<='Z'));
	}
	bool IsSame(char s , char d)
	{
	return (s == d)||(abs(s-d)=='a'-'A');
	}
	bool IsPanlindrome(const char * str, int length)
	{
	int s = 0;
	int e = length;
	while (s < e)
	{
	if (!IsAlphabet(str[s]))
	{
	s++;
	continue;
	}
	if (!IsAlphabet(str[e]))
	{
	e--;
	continue;
	}
	if (!IsSame(str[s++], str[e--]))
	return false;
	}
	return true;
	}

view raw panlindrome.cpp hosted with ❤ by GitHub

end of the code

UPDATE(2019-07-31): Solved the problem again. Had a bug in the logic.

	def is_panlindrome(sentence):
	s = 0
	e = len(sentence) - 1
	while s < e:
	if sentence[s].isalpha() != True:
	#skip the current char.
	s += 1
	continue
	if sentence[e].isalpha() != True:
	#skip the current char
	e -= 1
	continue
	#now both s and e points to alphabet. compare.
	if sentence[s].lower() != sentence[e].lower():
	return False
	s+=1
	e-=1
	return True
	inputs = [
	'A car, a man, a maraca.',
	'A dog, a plan, a canal: pagoda.',
	'A dog! A panic in a pagoda!',
	'A lad named E. Mandala',
	'A man, a plan, a canal: Panama.',
	'A man, a plan, a caanal: Panama.' # not palnindrome
	]
	for input in inputs:
	print("input = {} is panlindrom = {}".format(input, is_panlindrome(input)))

view raw facebook_check_if_panlindrome.py hosted with ❤ by GitHub

Practice statistics

7:15: to write up the code
2:10: to debug the code. (1 bug in the while loop)

UPDATE(2022-06-22): Solve the problem again.

	# code
	def is_alphabet(c):
	return c >= 'a' and c <= 'z' # 'a' <= c <= 'z'
	def is_palindrome(input):
	first = 0
	last = len(input) - 1
	input = input.lower()
	while first <= last:
	if is_alphabet(input[first]) != True:
	# skip the crrent char on left
	first = first + 1
	elif is_alphabet(input[last]) != True:
	last = last - 1
	elif input[first] == input[last]:
	first = first + 1
	last = last - 1
	else:
	return False
	return True
	# test
	input ="A car, a man, a maraca."
	result = is_palindrome(input)
	print ("is [{}] palindrome ? {}".format(input, result))
	input ="A dog, a plan, a canal: pagoda."
	result = is_palindrome(input)
	print ("is [{}] palindrome ? {}".format(input, result))
	input ="A dog! A panic in a pagoda!"
	result = is_palindrome(input)
	print ("is [{}] palindrome ? {}".format(input, result))
	input ="A lad named E. Mandala"
	result = is_palindrome(input)
	print ("is [{}] palindrome ? {}".format(input, result))
	input ="A man, a plan, a canal: Panama."
	result = is_palindrome(input)
	print ("is [{}] palindrome ? {}".format(input, result))

view raw check_if_palindrome.py hosted with ❤ by GitHub

06:42: for algorithm and pseudo code

07:08: coding

03:30: code review