Longest Palindromic Substring(最长回文)
程序员文章站
2024-02-24 17:51:58
...
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.
Example 2:
Input: “cbbd”
Output: "bb
/**
* 暴力**:遍历截取字符串,并将截取到的字符串进行反转,与原字符串相比是否相等
* 如果相等则是回文,直到找到长度最大的回文字符串为止
* @param s
* @return
*/
public static String LongestPalindromicSubstring1(String s)
{
if(s.length() == 0 || s == null) return "";
if(s.length() < 2) return s;
String temp1 = null;
String temp2 = null;
String result = s.substring(0,1);
for(int i =0; i < s.length();i++)
{
temp1 = null;
temp2 = null;
for(int j = s.length(); j>=i;j--)
{
if(j-i<result.length()) break;
temp1 = s.substring(i,j);
temp2 = new StringBuilder(temp1).reverse().toString();
if(temp1.equals(temp2)&&temp1.length() > result.length())
result = temp1;
}
}
return result;
}
/**
* 动态规划:记录前面的字符串是否为回文,是则保存为True,反之则保存为false。
* 在进入下一次判断时,如果首尾两个字符串相等,则只需判断它相邻的字符串是否为回文即可。
* abcba:在进行到a a 时,只需比较bcb是否为回文。
* 因此,需要一个二维boolean数组来保存某一字符串是否为回文
* @param s
* @return
*/
public static String LongestPalindromicSubstring2(String s)
{
if (s.length() == 0 || s == null) return "";
if(s.length() < 2) return s;
boolean [][] temp = new boolean[s.length()][s.length()];
String result = s.substring(0,1);
for(int i = 0; i < s.length(); i++)
{
for(int j = 0; j <= i;j++)
{
temp[j][i] = s.charAt(i) == s.charAt(j) &&(i-j <=2 || temp[j+1][i-1]);
if(temp[j][i])
{
if(i-j+1 > result.length())
{
result = s.substring(j,i+1);
}
}
}
}
return result;
}
/**
* 中心扩展算法,一个字符串中存在有两个中心的情况,因此ExpandAroundCenter需要执行两次
* @param s
* @return
*/
public static String LongestPalindromicSubstring3(String s)
{
if(s.length() ==0 || s == null) return "";
if(s.length() < 2) return s;
int start = 0;
int end = 0;
for(int i = 0; i < s.length()-1; 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);
}
/**
* 以某一位置为中心向两边扩展
* @param s
* @param left
* @param right
* @return
*/
public static int ExpandAroundCenter(String s, int left, int right)
{
int L = left;
int R = right;
while(L >=0 && R < s.length() && s.charAt(L) == s.charAt(R))
{
L--;
R++;
}
return R-L-1;
}
static StringBuilder longest = new StringBuilder("");
/**
* 中心扩展算法的另一种写法
* @param s
* @return
*/
public static String LongestPalindromicSubstring4(String s)
{
if (s.length() <= 1) return s;
for (int i = 0; i < s.length(); i++) {
expand(s, longest, i, i); //odd
expand(s, longest, i, i + 1); //even
}
return longest.toString();
}
private static void expand(String s, StringBuilder longest, int i, int j) {
while (i >= 0 && j < s.length()) {
if (s.charAt(i) == s.charAt(j)) {
if (j - i + 1 > longest.length()) {
//删除longest原有的字符串
longest.delete(0, longest.length());
//重新向longest中添加字符串
longest.append(s.substring(i, j + 1));
}
//向两边扩展
i--;
j++;
}
else
break;
}
}
推荐阅读
-
LeetCode 5. Longest Palindromic Substring(最长回文子串)
-
【LeetCode】#5最长回文子串(Longest Palindromic Substring)
-
Longest Palindromic Substring(最长回文)
-
Leetcode 5. Longest Palindromic Substring 最长回文子串
-
leetcode 5st Longest Palindromic Substring
-
LeetCode-5. Longest Palindromic Substring(三种解法及Manacher算法详解)
-
LeetCode 3-- 无重复字符的最长子串 ( Longest Substring Without Repeating Characters )
-
【小白爬Leetcode5】最长回文子串 Longest Palindromic Substring
-
5. Longest Palindromic Substring Go语言
-
go语言解leetcode习题 5. Longest Palindromic Substring