一、题目
二、思路
审题看清楚,,题目问的不是回文子串,不是子串!!!
暴力解法会超时,可以使用双指针:
如果当前左右指针指向的元素不相等,可以试着判断删除掉左元素或者右元素后的字符串是否为回文字符串,注意此时i左边和j右边是已经判断完了(再重复一次!判断的不是回文子串);
如果当前左右指针指向的元素相等,则左指针向右一格,右指针向左一格。
每次两指针表示的字符判断相等,则该部分就符合回文串,贪心思想。
注意s.substr(a, b)表示从s字符串的a下标开始算,连续b个字符。
三、代码
class Solution { public: bool validPalindrome(string s) { int i = 0; int j = s.size() - 1; while(i < j){ if(s[i] != s[j]){ return isPalindrome(s, i + 1, j) || isPalindrome(s, i, j - 1); } i++; j--; } return true; } //法一 bool isPalindrome(string s, int i, int j){ string temp = s.substr(i, j - i + 1); reverse(temp.begin(), temp.end()); return temp == s.substr(i, j - i + 1); } //法二 bool isPalindrome1(string& s,int i, int j){ while(i < j){ if(s[i++] != s[j--]){ return false; } } return true; } };