【LeetCode】#5最长回文子串(Longest Palindromic Substring)
程序员文章站
2024-02-24 17:51:52
...
【LeetCode】#5最长回文子串(Longest Palindromic Substring)
题目描述
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
示例
示例1:
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.
示例2:
输入: “cbbd”
输出: “bb”
Input: “cbbd”
Output: “bb”
解法
class Solution{
public String longestPalindrome(String s){
if(s==null || s.length()<1)
return "";
int start = 0, end = 0;
for(int i=0; i<s.length(); i++){
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i+1);
int len = Math.max(len1, len2);
if(len>end-start){
start = i - (len-1)/2;
end = i + len/2;
}
}
return s.substring(start, end+1);
}
private int expandAroundCenter(String s, int left, int right){
int L = left, R = right;
while(L>=0 && R<s.length() && s.charAt(L)==s.charAt(R)){
L--;
R++;
}
return R-L-1;
}
}
推荐阅读
-
LeetCode 5. Longest Palindromic Substring(最长回文子串)
-
【LeetCode】#5最长回文子串(Longest Palindromic Substring)
-
Longest Palindromic Substring(最长回文)
-
Leetcode 5. Longest Palindromic Substring 最长回文子串
-
leetcode 5st Longest Palindromic Substring
-
5. 最长回文子串 mark
-
leetcode 5.最长回文子串(中等,动态规划)
-
中等- LeetCode 5.最长回文子串
-
最长回文子串 LeetCode
-
leetcode最长回文子串