4
5. 最长回文子串
source link: https://leetcode.cn/problems/longest-palindromic-substring/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
5. 最长回文子串 - 力扣（LeetCode）
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd" 输出："bb"
提示：
1 <= s.length <= 1000s仅由数字和英文字母组成
通过次数1,174,595提交次数3,167,185
显示提示1
How can we reuse a previously computed palindrome to compute a larger palindrome?
显示提示2
If “aba” is a palindrome, is “xabax” a palindrome? Similarly is “xabay” a palindrome?
显示提示3
Complexity based hint:
If we use brute-force and check whether for every start and end position a substring is a palindrome we have O(n^2) start - end pairs and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(1) by reusing some previous computation.
If we use brute-force and check whether for every start and end position a substring is a palindrome we have O(n^2) start - end pairs and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(1) by reusing some previous computation.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK