C++面试宝典第15题：最长回文子串

2024-01-08 07:29:02

题目

        回文是一个正读和反读都相同的字符串，比如："aba"是回文，而"abc"不是回文。现给定一个字符串s，找出s中最长的回文子串（可能有多个最长的，找出一个即可）。

        示例 1：

输入: "babad"
输出: "bab"（"aba" 也是一个有效答案）

        示例 2：

输入: "cbbd"
输出: "bb"

解析

        最长回文子串是一道比较常见和经典的面试题，有好几种不同的解法。每种解法的时间复杂度和空间复杂度可能都不相同，下面分别进行介绍。

        最直接、最简单的方法，就是暴力求解法。暴力求解法会遍历子字符串的起始位置和结束位置，再判断起始位置和结束位置之间的子字符串是否为回文。具体实现，可参考下面的示例代码。

#include <iostream>
using namespace std;

bool IsPalindrome(const string &strText, int nStart, int nEnd)
{
    while (nStart < nEnd)

文章来源:https://blog.csdn.net/hope_wisdom/article/details/135443383
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。