首页 > 代码库 > Leetcode 5. Longest Palindromic Substring

Leetcode 5. Longest Palindromic Substring

2024-11-06 06:44:39   203人阅读

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

 

Similar Questions: Shortest Palindrome Palindrome Permutation Palindrome Pairs Longest Palindromic Subsequence Palindromic Substrings 

Next challenges: Palindrome Permutation Palindrome Pairs Longest Palindromic Subsequence

 

思路：对原字符串运行"马拉车"算法（Manacher‘s Algorithm），找到最长回文子串的中心位置所在，然后向两边扩充还原。

 

关于Manacher‘s Algorithm的学习资料：

https://segmentfault.com/a/1190000003914228

http://www.cnblogs.com/grandyang/p/4475985.html

 

代码：

 1 public class Solution {
 2     public String longestPalindrome(String s) {
 3         int maxRight = 0, pos = 0, maxLen = 0, maxPos = 0;
 4         String rs = "#";
 5         for(int i = 0; i < s.length(); i++) rs = rs + s.charAt(i) + "#";
 6         int[] RL = new int[rs.length()];
 7         for(int i = 0; i < rs.length(); i++) {
 8             if(maxRight > i) RL[i] = Math.min(maxRight - i, RL[2 * pos - i]);
 9             while(i - RL[i] - 1>= 0 && i + RL[i] + 1< rs.length() && rs.charAt(i - RL[i] - 1) == rs.charAt(i + RL[i] + 1)) RL[i]++;
10             if(RL[i] + i > maxRight) {
11                 pos = i;
12                 maxRight = RL[i] + i;
13             }
14             if(maxLen < 2 * RL[i] + 1) {
15                 maxLen = 2 * RL[i] + 1;
16                 maxPos = i;
17             }
18         }
19         return rs.substring(maxPos - RL[maxPos], maxPos + RL[maxPos] + 1).replace("#","");
20     }
21 }

 

Leetcode 5. Longest Palindromic Substring


联系
我们