【题目来源】
https://www.luogu.com.cn/problem/B2124
【题目描述】
输入一个字符串,输出该字符串是否回文。回文是指顺读和倒读都一样的字符串。
【输入格式】
输入一行字符串,长度小于 100。
【输出格式】
如果字符串是回文,输出 yes;否则,输出 no。
【输入样例】
abcdedcba
【输出样例】
yes
【算法分析】
● 双指针算法的核心思想
双指针算法的本质是:用两个指针(索引)在一个 / 多个序列(数组、字符串、链表)中移动,通过指针的 “同向 / 反向 / 相向” 移动,替代暴力枚举的嵌套循环,将时间复杂度从 O (n²) 优化到 O (n)。
● 本题简单的方法是利用函数reverse(s.begin(),s.end());对字符串 s 进行回文判断。
● 本题利用顺序栈求解的代码,详见:https://blog.csdn.net/hnjzsyjyj/article/details/145522672
【算法代码一:STL stack】
#include <bits/stdc++.h> using namespace std; stack<char> stk; int main() { string s; cin>>s; for(char t:s) stk.push(t); for(char t:s) { if(t==stk.top()) stk.pop(); else { cout<<"no"; return 0; } } cout<<"yes"; return 0; } /* in:abcdedcba out:yes */【算法代码二:双指针】
#include <bits/stdc++.h> using namespace std; int main() { string s; cin>>s; int i=0,j=s.size()-1; while(i<j) { if(s[i]==s[j]) i++,j--; else { cout<<"no"; return 0; } } cout<<"yes"; return 0; } /* in:abcdedcba out:yes */【算法代码三:reverse】
#include <bits/stdc++.h> using namespace std; int main() { string s,t; cin>>s; t=s; reverse(s.begin(),s.end()); if(s==t) cout<<"yes"<<endl; else cout<<"no"<<endl; return 0; } /* in:abcdedcba out:yes */
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/145522672
https://blog.csdn.net/hnjzsyjyj/article/details/158466396