680验证回文字符串

题目地址 题目地址如上

题目描述

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例 1:

输入: “aba” 输出: True 示例 2:

输入: “abca” 输出: True 解释: 你可以删除c字符。 注意:

字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

题目分析

首先题目大致的解题方向是双指针。通过头尾双指针遍历，判断是否为回文字符串。这个相信大家都不陌生。代码如下

bool ishui(string s){ int i = 0 , j = s.length() - 1; while(i<j){ if(s[i]==s[j]){ //遇到相同的直接指针移动 i++; j--; }else{ return false; //可以肯定 绝对不是回文字符串 } } return true; }

其次我们需要解决的是当头尾指针不一样的时候会发生的情况，首先明确一点，当头尾指针不一样时，头尾指针之前的字符肯定是一样的，因为是依次一一遍历的，比如 abecbdba，当指针在e和d处时，它们前面的ba一定是回文的。所以我们删除某个字符后我们只需要比较子串是否回文即可。代码如下

bool validPalindrome(string s) { int i = 0 , j = s.length() - 1; while(i < j){ if(s[i]==s[j]){ i++; j--; }else{ return ishui(s.substr(i+1,j-i))||ishui(s.substr(i,j-i))) } } return true; }