アルゴリズム問題を解く 13 - 回文

問題

Please implement a function that checks whether a positive number is a palindrome or not.
For example, 121 is a palindrome, but 123 is not. Please write an answer in C.
( Coding interviewsより抜粋 )

ヒント

山本山，とかたけやぶやけた，に共通するのは，文字列長が奇数であることである．この問題はマイナスでない整数であることも忘れずに．

答え1

先頭と最後尾，先頭+1と最後尾-1..を比較していけばよいのでO(N/2)の計算量でよい．
NULLの場合，負の場合等々といったチェックも忘れずに．

#include <cstdio>
#include <cstdlib>
#include <string>

int isdigits(const char* const s, int len) {

 int result = 1;
 for( int i = 0;i < len;i++ ) {
  if( !isdigit(s[i]) ) {
   result = 0;
   break;
  }
 }

 return result;

}

int ispalindrome(const char* const s, unsigned int len) {

 // prerequisite check
 if( s[0] == '-' ||
  !(len % 2) ||
  len == 1 ||
  s == NULL ||
  !isdigits(s,len))
  return 0;
  
 int result = 1;
 unsigned int half = len >> 1;
 for( unsigned int i = 0;i < half;i++ ) {
  if(s[i] != s[len-1-i]) {
   result = 0;
   break;
  }
 }
 return result;
}

int main() {

 char* s1 = "142";
 char* s2 = "5";
 char* s3 = "282";
 char* s4 = "2820";
 char* s5 = "-10";
 char* s6 = "ABA";
 printf("%d\n",ispalindrome(s1,strlen(s1)));
 printf("%d\n",ispalindrome(s2,strlen(s2)));
 printf("%d\n",ispalindrome(s3,strlen(s3)));
 printf("%d\n",ispalindrome(s4,strlen(s4)));
 printf("%d\n",ispalindrome(s5,strlen(s5)));
 printf("%d\n",ispalindrome(s6,strlen(s6)));

 char ch;
 scanf(&ch);
}

答え2

答え１よりはるかに優れたコードである．

#include <cstdio>
#include <cstdlib>
#include <string>

int ispalindrome(unsigned int n) {

 if( n <= 110 )
  return 0;

 unsigned int orig = n;
 unsigned int rev = 0;
 while( n != 0 ) {
  rev = rev * 10 + n % 10;
  n /= 10;
 }

 return (rev == orig) ? 1 : 0;

}

int main() {

 unsigned int s1 = 142;
 unsigned int s2 = 5;
 unsigned int s3 = 282;
 unsigned int s4 = 2820;
 unsigned int s5 = 111;

 printf("%d\n",ispalindrome(s1));
 printf("%d\n",ispalindrome(s2));
 printf("%d\n",ispalindrome(s3));
 printf("%d\n",ispalindrome(s4));
 printf("%d\n",ispalindrome(s5));

}