最长回文子串

​ 給一个字符串s，找到s中的最长的回文子串

最长回文子串和回文子串

5. 最长回文子串

class Solution {
public:
    //定义一个函数来寻找最长回文串
    string palindrome(string s, int l, int r) {
    // 防止索引越界
    while (l >=0 && r < s.size() && s[l] == s[r]) {
        // 双指针，向两边展开
        l--; 
        r++;
    }
    // 返回以 s[l] 和 s[r] 为中心的最长回文串
    return s.substr(l+1, r-l-1);
    }

    string longestPalindrome(string s) {
    string res;
    for (int i = 0; i < s.size(); i++) {
        // 以 s[i] 为中心的最长回文子串
        string s1 = palindrome(s, i, i);
        // 以 s[i] 和 s[i+1] 为中心的最长回文子串
        string s2 = palindrome(s, i, i + 1);
        // res = longest(res, s1, s2)
        res = res.size() > s1.size() ? res : s1;
        res = res.size() > s2.size() ? res : s2;
    }
    return res;
    } 
};

时间复杂度：O(N^2^)

空间复杂度：O(1)

647. 回文子串

class Solution {
public:
    int countSubstrings(string s) {
        int result=0;
        for(int i=0; i<s.size(); i++){
            int a=Substring(s,i,i);
            int b=Substring(s,i,i+1);
            result += a+b;
        }
        return result;
    }

    int Substring(string s, int left, int right){
        int result=0;
        while(left>=0 && right<s.size() && s[left]==s[right]){
            left--;
            right++;
            result++;
        }
        return result;
    }
};

时间复杂度：O(N^2^)

空间复杂度：O(1)

125. 验证回文串

class Solution {
public:
    bool isPalindrome(string s) {
        //双指针
        string res;
        for(char ch : s){
            if(isalnum(ch)){  //是否是字母和数字
                res += tolower(ch); //tolower()将大写转换成小写
            }
        }
        int n=res.size();
        int left = 0;
        int right = n-1;
        while(left<right){
            if(res[left]!=res[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};