|
（一）题目描述
给你一个字符串?s，找到?s?中最长的回文子串。
（二）思路
1）暴力解法：
利用二重循环，对该字符串的每个子序列进行判断。
//直接利用二重循环，遍历每一个子串，并判断其是否为回文串
class Solution03{
public String longestPalindrome(String s) {
int len=s.length();
if(len<2){
return s;
}
int manLen=1;
int begin=0;
for (int i = 0; i < len-1; i++) {
for (int j = i+1; j < len; j++) {
if(i<j&&hwStr(s,i,j)){
if(j-i+1>manLen){
begin=i;
manLen=j-i+1;
}
}
}
}
return s.substring(begin,begin+manLen);
}
//判断是否为回文串的函数
public boolean hwStr(String s,int begin,int end){
char[] array=s.toCharArray();
while (begin<end){
if(array[begin]!=array[end]){
return false;
}
begin++;
end--;
}
return true;
}
}
2）动态规划
? ? ?1、定义数组元素dp[i][j]：i、j之间的字符串是否为回文串（dp[i][j]=true或false）
? ? ?2、找出数组元素间的关系式：dp[i][j]=dp[i+1][j-1]（看中间的字符串是否为回文串）
? ? ?3、初始值：i=j时，dp[i][j]=true
class Solution02 {
public String longestPalindrome(String s) {
int len=s.length();
Boolean[][] dp=new Boolean[len][len];
if(len<2){
return s;
}
// (1)初始值
for (int i = 0; i < len; i++) {
dp[i][i]=true;
}
char[] array=s.toCharArray();
int Maxlen=1;
int begin=0;
// (2)递推式
// 为什么j要在前？因为递推公式需要只带dp[i+1][j-1]的值，
for (int j = 1; j < len; j++) {
for (int i = 0; i < j; i++) {
if (array[i]!=array[j]){
dp[i][j]=false;
}else{
//j-i<3说明两字符中间有1或0个字符，而此时边界两字符相等所以无须判断了
if(j-i<3){
dp[i][j]=true;
}else{
dp[i][j]=dp[i+1][j-1];
}
if(j-i+1>Maxlen&&dp[i][j]){
Maxlen=j-i+1;
begin=i;
}
}
}
}
return s.substring(begin,begin+Maxlen);
}
}
?附上解析链接：力扣
?
|