回文判断

题目描述

回文，英文palindrome，指一个顺着读和反过来读都一样的字符串，比如madam、我爱我，这样的短句在智力性、趣味性和艺术性上都颇有特色，中国历史上还有很多有趣的回文诗。

那么，我们的第一个问题就是：判断一个字串是否是回文？

分析与解法

解法一：

使用两个指针分别指向字符串的头尾，同时向中间遍历字符串，如果所有字符均相同，则是回文，代码如下：

 1 bool IsPalindrome(const char *str){
 2     if (str == nullptr)
 3         return false;
 4 
 5     int length = strlen(str);
 6     const char *begin = str;
 7     const char *end = begin + length - 1;
 8 
 9     while (begin < end){
10         if (*begin != *end)
11             return false;
12         ++begin;
13         --end;
14     }
15     return true;
16 }
时间复杂度为O(n),空间复杂度为O(1)

解法二：
从中间开始分别向两头遍历，检查字符是否都相同，代码如下：

 1 bool IsPalindrome2(const char *str){
 2     if (str == nullptr)
 3         return false;
 4 
 5     int length = strlen(str);
 6     if (length < 1)
 7         return false;
 8 
 9     const char *first, *second;
10     int mid = length >> 1;
11     first = str + mid - 1;
12     second = str + length - mid;
13 
14     while (first >= str){
15         if (*first-- != *second++)
16             return false;
17     }
18     return true;
19 }
时间复杂度也为O(n),空间复杂度为O(1)