(十一)字符串【C++刷题】
2021/12/31 14:37:07
本文主要是介绍(十一)字符串【C++刷题】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
最长回文子串
Leetcode:5,https://leetcode-cn.com/problems/longest-palindromic-substring/)
1.问题描述
给定一个字符串s,找到s中最长的回文子串。【回文串:正着读和反着读都一样】
2.输入输出
- Input:s = "babad"
- Output:"bab"
3.算法分析
从中心点往两边扩散,来寻找回文串,这种方式相当于穷举每一个点为中心点。若回文串是奇数,则中心点只有一个;若回文串是偶数,则中心点有两个。即先确定中心点后去找回文串,将每次找到的回文串与之前的做对比,留下最长的。
- 时间复杂度:O(n)
- 空间复杂度:O(1)
4.编程实现
#include <iostream> #include <string> using namespace std; class Solution { public: string longestPalindrome(string s) { int len = s.size(); if (len < 2) return s; int start = 0, maxlen = 1, mid = 0; while (mid < len) { // 穷举每个中心点 int mid_start = mid, mid_end = mid; while (mid_end+1 < len && s[mid_end] == s[mid_end+1]) mid_end++; mid = mid_end+1; int left = mid_start, right = mid_end; while (left-1 >= 0 && right+1 < len && s[left-1] == s[right+1]) { left--; right++; } int curlen = right - left + 1; if (curlen > maxlen) { maxlen = curlen; start = left; } } return s.substr(start, maxlen); } }; int main() { Solution sol; string s; cin >> s; cout << sol.longestPalindrome(s) << endl; return 0; }
这篇关于(十一)字符串【C++刷题】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享