判断回文串

---

原题目

尺取法——反向扫描

#include <bits/stdc++.h>  
using namespace std;
int main(){
  int n; cin >> n;                  //n是测试用例个数
  while(n--){
    string s;  cin >> s;            //读一个字符串
    bool ans = true;                //测试结果初始化
    int i = 0, j = s.size() - 1;    //双指针
    while(i < j){ 
      if(s[i] != s[j]) { ans = false; break; }  //双指针字母不同，变量设为F，并跳出循环
      i++; j--;                     //移动双指针
    }
    if(ans) cout << "yes" << endl;
    else cout << "no" << endl;
  }
  return 0;
}

笔记：双指针的反向扫描就是首尾开始，中间交汇，扫描不需要占用额外的空间

类似题目1：

尺取法——反向扫描

#include <bits/stdc++.h> 
using namespace std;
int main(){
  int n; cin >> n;         
  while(n--){
    string s; cin >> s;    
    bool ans = true;      
    int i = 0, j = s.size() - 1;
    while(i < j){ 
      //修改部分
      while (i < j && !isalpha(s[i])) ++i;      //非英文字母就跳过
      while (i < j && !isalpha(s[j])) --j;      
      if (i < j) {
        if (tolower(s[i]) != tolower(s[j])) ans = false; break;   //把字母字符转换成小写
        ++i;
        --j;
      }
    }
    if(ans) cout << "yes" << endl;
    else cout << "no" << endl;
  }
  return 0;
}

笔记：isalpha()检查元素只包含字母才会返回True，元素需要字母+数字可以使用isalnum()

类似题目2

尺取法——反向扫描

#include <bits/stdc++.h>
using namespace std;

bool compare(string s, int low, int high) {       //移除掉多余字符后继续比较头尾字符
  for (int i = low, j = high; i < j; ++i, --j) {
    if (s[i] != s[j]) {
      return false;
    }
  }
  return true;
}

int main() {
  int n;
  cin >> n; 
  while (n--) {
    string s;
    cin >> s; 
    bool ans = true; 
    int i = 0, j = s.size() - 1; 
    while (i < j) {
      while (i < j && !isalpha(s[i])) ++i;
      while (i < j && !isalpha(s[j])) --j;
      if (i < j) {
        if (tolower(s[i]) != tolower(s[j])) {
          //修改部分
          ans = compare(s, i, j - 1) || compare(s, i + 1, j);
          break; //发现第一对不一样的字符之后，要么删左边的，要么删右边的。
        }
        ++i;
        --j;
      }
    }
    if (ans) cout << "yes" << endl;
    else cout << "no" << endl;
  }
  return 0;
}

笔记：在发现双指针的指向元素不同时，删掉左指针或者右指针后再判断是否是回文串