- // 从左右两边开始比较判断
- #include<iostream>
- #include<string.h>
- using namespace std;
- const int MAXN = 1e5;
- bool is_palindrome(char *s, int len)
- {
- if(s == NULL || len <1) // 非法输入
- return false;
- char *front, *tail; // 首尾指针
- // 指针声明了就要记得初始化
- front = s;
- tail = s + len - 1;
- while(front < tail)
- {
- if(*front != *tail)
- return false;
- front++;
- tail--;
- }
- return true;
- }
- int main()
- {
- char str[MAXN];
- while(cin>> str)
- {
- int len = strlen(str);
- cout <<is_palindrome(str, len) << endl;
- }
- return 0;
- }
- // 时间复杂度 O(n), 空间复杂度 O(1)
- // 从中间开始往两边判断
- #include<iostream>
- #include<string.h>
- using namespace std;
- const int MAXN = 1e5;
- bool is_palindrome(char *s, int len)
- {
- if(s == NULL || len <1)
- return false;
- char *left, *right;
- int mid = ((len>> 1) - 1)>= 0 ? (len>> 1) - 1 : 0;
- left = s + mid;
- right = s + len - 1 - mid;
- while(left>= s)
- {
- if(*left != *right)
- return false;
- left--;
- right++;
- }
- return true;
- }
- int main()
- {
- char str[MAXN];
- while(cin>> str)
- {
- int len = strlen(str);
- cout << is_palindrome(str, len) << endl;
- }
- return 0;
- }
- // 时间复杂度 O(n), 空间复杂度 O(1)
上面两种判断回文的方法在复杂度上没有区别, 都是 O(n) 的时间复杂度和 O(1) 的空间复杂度. 但是第二种从中间往两边判断的方法在解决一些问题时有独到之处.
来源: http://www.bubuko.com/infodetail-2850404.html