# Palindrome detection

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Palindrome detection
You are encouraged to solve this task according to the task description, using any language you may know.

Write at least one function/method (or whatever it is called in your preferred language) to check if a sequence of characters (or bytes) is a palindrome or not. The function must return a boolean value (or something that can be used as boolean value, like an integer).

It is not mandatory to write also an example code that uses the function, unless its usage could be not clear (e.g. the provided recursive C solution needs explanation on how to call the function).

It is not mandatory to handle properly encodings (see String length), i.e. it is admissible that the function does not recognize 'salàlas' as palindrome.

The function must not ignore spaces and punctuations.

An example of latin palindrome is the sentence "In girum imus nocte et consumimur igni", roughly translated as: we walk around in the night and we are burnt by the fire (of love). To do your test with it, you must make it all the same case and strip spaces.

## C

### Non-recursive

This function compares the first char with the last, the second with the one previous the last, and so on. The first different pair it finds, return 0 (false); if all the pairs were equal, then return 1 (true).

<c>int palindrome(char *s) {

```  int i,l;
for(l=0; s[l]!=0; l++) ;
for(i=0; i<l; i++)
{
if ( s[i] != s[l-i-1] ) return 0;
}
return 1;
```

}</c>

### Recursive

A single char is surely a palindrome; a string is a palindrome if first and last char are the same and the remaining string (the string starting from the second char and ending to the char preceding the last one) is itself a palindrome.

<c>int palindrome_r(char *s, int b, int e) {

```  if ( e <= 1 ) return 1;
if ( s[b] != s[e-1] ) return 0;
return palindrome_r(s, b+1, e-1);
```

}</c>

### Testing

<c>#include <stdio.h> /* testing */ int main() {

```  char *t = "ingirumimusnocteetconsumimurigni";
char *template = "sequence \"%s\" is%s palindrome\n";
int l;

for(l=0; t[l]!=0; l++) ;
printf(template,
t, palindrome(t) ? "" : "n't");
printf(template,
t, palindrome_r(t, 0, l) ? "" : "n't");
return 0;
```

}</c>

### Non-recursive

A string is a palindrome if reversing it we obtain the same string.

```is_palindrome x | x == reverse x = True | otherwise = False```

### Recursive

See the C palindrome_r code for an explanation of the concept used in this solution.

```is_palindrome_r x | length x <= 1 = True | head x == last x = is_palindrome_r (drop 1 (take ((length x)-1) x)) | otherwise = False```

## Perl

### Non-recursive

One solution (palindrome_c) is the same as the C non-recursive solution palindrome; while Perl palindrome sub uses the idea that a word is a palindrome if, once reverted, it looks the same as the original word (this is the definition of a palindrome).

<perl>sub palindrome {

``` my @s = split //, shift(@_);
if ( join("", @s) eq join("",reverse(@s)) ) { return 1; }
return 0;
```

}

sub palindrome_c {

``` my @s = split //, shift(@_);
my \$l = scalar(@s);
for(my \$i; \$i < \$l; \$i++)
{
if ( \$s[\$i] ne \$s[\$l - \$i - 1] ) { return 0; }
}
return 1;
```

}</perl>

### Recursive

<perl>sub palindrome_r {

``` my @s = split//, shift(@_);
if ( length(@s) <= 1 ) { return 1; }
pop(@s);   # strip the last char
shift(@s); # strip the first char
return palindrome_r(join("",@s));
```

}</perl>

### Testing

<perl>sub mtest {

```  my ( \$t, \$func ) = @_;
printf("sequence \"%s\" is%s palindrome\n",
\$t, &\$func(\$t) ? "" : "n't");
```

} mtest "ingirumimusnocteetconsumimurigni", \&palindrome; mtest "ingirumimusnocteetconsumimurigni", \&palindrome_r; mtest "ingirumimusnocteetconsumimurigni", \&palindrome_c;

exit 0;</perl>

## Python

### Non-recursive

This one uses the reversing the string technics (to revert a string Python can use the odd but right syntax string[::-1])

<python>def is_palindrome(s):

``` if s == s[::-1]:
return True
else:
return False</python>
```

### Recursive

<python>def is_palindrome_r(s):

``` if len(s) <= 1:
return True
else:
return is_palindrome_r(s[1:len(s)-1])</python>
```

### Testing

<python>def tostring(t):

``` if t:
return "True"
else:
return "False"
```

p = "ingirumimusnocteetconsumimurigni" print "'" + p + "' is palindrome? " + tostring(is_palindrome(p)) print "'" + p + "' is palindrome? " + tostring(is_palindrome_r(p))</python>