C/C++面试宝典:求字符串的最大长度回文

liuian 2025-07-07 20:09 23 浏览

引言

字符串回文是C/C++面试中常见的问题之一，该内容主要考察面试者对于代码设计的鲁棒性、时间复杂度和空间复杂度的考虑，同时需要对代码的异常做和是判断，想要实现相关的代码不难，但是想要设计出鲁棒性较好的代码，需要花费一定的形式

示例需求描述

对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。

代码设计思路：通过回文字符串的特性，正反读取都相同，可以将字符串逆转后，求取最长公共子串，但可能会出现其他部分重置与另一部分相同，所以需要对比找到最长公共子串的索引与原索引相加是否为字符串长度-1,即当A.at(right + 1) == A.at(left - 1)时，maxLen = right - left + 1;

测试用例：

示例1

输入：

"ababc"

返回值：

说明：

最长的回文子串为"aba"与"bab"，长度都为3

示例2

输入：

"abbba"

返回值：

示例3

输入：

"b"	返回值：1

示例代码：

int getLongestPalindrome(string A, int n) 
  {
       //边界条件判断
    if (n < 2)
        return A.length();
    //maxLen表示最长回文串的长度
    int maxLen = 0;
    for (int i = 0; i < n; ) {
        //如果剩余子串长度小于目前查找到的最长回文子串的长度，直接终止循环
        // （因为即使他是回文子串，也不是最长的，所以直接终止循环，不再判断）
        if (n - i <= maxLen / 2)
            break;
        int left = i;
        int right = i;
        while (right < n - 1 && A.at(right + 1) == A.at(right))
            ++right; //过滤掉重复的
  
        //下次在判断的时候从重复的下一个字符开始判断
        i = right + 1;
        //然后往两边判断，找出回文子串的长度
        while (right < n - 1 && left > 0 && A.at(right + 1) == A.at(left - 1)) {
            ++right;
            --left;
        }
        //保留最长的
        if (right - left + 1 > maxLen) {
            maxLen = right - left + 1;
        }
    }
    //截取回文子串
    return maxLen;
    }
};

结语

对于一个一个字符串的最大回文的计算，我们也可以使用的是中心位置法，遍历去头去尾的字符串，若字符串左边右边相等，则两个指针定位左边右边，同时向外扩展直到不相等，则回文长度是right_point - left_point - 1；若字符串左边或者右边的某一位与该字符串相等，则指针定位这两个相等的字符，并同时向外扩展直到不相等，方法相同。

c++ 字符串查找

C/C++面试宝典:求字符串的最大长度回文

引言

示例需求描述

结语

相关推荐

Python实现人事自动打卡，再也不会被批评

【验证码逆向专栏】vaptcha 手势验证码逆向分析

Psutil + Flask + Pyecharts + Bootstrap 开发动态可视化系统监控

一个解决支持HTML/CSS/JS网页转PDF(高质量)的终极解决方案

再见Swagger UI 国人开源了一款超好用的 API 文档生成框架，真香

网页转成pdf文件的经验分享网页转成pdf文件的经验分享怎么弄

C++ std::vector 简介

飞牛OS入门安装遇到问题，如何解决?

系统C盘清理:微信PC端文件清理，扩大C盘可用空间步骤

10款高性能NAS丨双十一必看，轻松搞定虚拟机、Docker、软路由

C/C++面试宝典:求字符串的最大长度回文

引言

示例需求描述

结语

相关推荐

Python实现人事自动打卡，再也不会被批评

【验证码逆向专栏】vaptcha 手势验证码逆向分析

Psutil + Flask + Pyecharts + Bootstrap 开发动态可视化系统监控

一个解决支持HTML/CSS/JS网页转PDF(高质量)的终极解决方案

再见Swagger UI 国人开源了一款超好用的 API 文档生成框架，真香

网页转成pdf文件的经验分享 网页转成pdf文件的经验分享怎么弄

C++ std::vector 简介

飞牛OS入门安装遇到问题，如何解决?

系统C盘清理:微信PC端文件清理，扩大C盘可用空间步骤

10款高性能NAS丨双十一必看，轻松搞定虚拟机、Docker、软路由

网页转成pdf文件的经验分享网页转成pdf文件的经验分享怎么弄