這篇文章主要介紹“如何編寫(xiě)代碼實(shí)現(xiàn)一個(gè)字符串的最長(zhǎng)回文子串”，在日常操作中，相信很多人在如何編寫(xiě)代碼實(shí)現(xiàn)一個(gè)字符串的最長(zhǎng)回文子串問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”如何編寫(xiě)代碼實(shí)現(xiàn)一個(gè)字符串的最長(zhǎng)回文子串”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！
網(wǎng)站建設(shè)哪家好，找創(chuàng)新互聯(lián)公司！專(zhuān)注于網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開(kāi)發(fā)、重慶小程序開(kāi)發(fā)、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項(xiàng)目。為回饋新老客戶(hù)創(chuàng)新互聯(lián)還提供了堆龍德慶免費(fèi)建站歡迎大家使用！
重慶分公司
重慶分公司
/**
* @author pxu
* @create 2021/4/7-2:28 下午
*/
public class Nc017 {
public static void main(String[] args) {
String str = "abc1234321ab";
Nc017 nc017 = new Nc017();
int longestPalindrome = nc017.getLongestPalindrome(str, str.length());
System.out.println(longestPalindrome);
}
public int getLongestPalindrome(String A, int n) {
/**
* 這個(gè)問(wèn)題用的是從上而下的動(dòng)態(tài)規(guī)劃求解方法，講求字符串A的最長(zhǎng)回文子序列問(wèn)題，
* 轉(zhuǎn)換成三個(gè)子問(wèn)題：求A.sutString(1,A.length)、求A.sutString(0,A.length-1)
* 以及A.sutString(1,A.length-1)三種情況的解，并比較三種情況的解，得到最優(yōu)解
*
* 首先驗(yàn)證參數(shù)合法性，在定義一個(gè)二維數(shù)組用于記錄已經(jīng)求結(jié)果的子問(wèn)題的解，主要的求解過(guò)程
* 在helper方法中
*/
switch (n)
{
case 0:
return 0;
case 1:
return 1;
default:
{
Optimum[][] dp = new Optimum[n][n];
Optimum optimum = helper(A, dp, 0, n - 1);
return optimum.len;
}
}
}
public Optimum helper(String theStr, Optimum[][] solArr, int start, int end)
{
/**
* 此方法的最終返回結(jié)果
*/
Optimum res = null;
/**
* 參數(shù)不合法直接返回null
*/
if(start<0 || end<0 || start>=solArr.length || end>=solArr.length || start > end)
return null;
else
{
/**
* 如果當(dāng)前子問(wèn)題已經(jīng)被求結(jié)果，直接返回在dp中記錄的結(jié)果
*/
if(solArr[start][end]!=null)
{
return solArr[start][end];
}
else if (start == end)
{
/**
* 用于處理只有一個(gè)字符的子串的情況
*/
res = new Optimum(start,end,theStr);
}
else
{
/**
* 分別求解三種子問(wèn)題的最優(yōu)解
*/
Optimum left = helper(theStr, solArr, start + 1, end);
Optimum right = helper(theStr, solArr, start, end - 1);
Optimum mid = helper(theStr, solArr, start + 1, end - 1);
/**
* 如果start位置和end位置的字符相等，那么需要對(duì)A.sutString(1,A.length-1)類(lèi)型問(wèn)題
* 的解進(jìn)一步處理
*/
if(theStr.charAt(start) == theStr.charAt(end))
{
/**
* 如果start和end是相鄰的整數(shù)，如6和7，那么從上面的代碼可以知道此時(shí)mid一定是null，
* 但是此時(shí)的start位置和end位置的字符相等，那么mid解應(yīng)該是一個(gè)長(zhǎng)度為2的回文串。
*
* 如果mid不是null，并且mid解的回文串的起止位置剛好和start和end相鄰，那么說(shuō)明該解
* 可以被進(jìn)一步延長(zhǎng)，吧start和end位置的字符也包括進(jìn)去。
*/
if(mid == null || (mid.start == start+1 && mid.end == end-1))
mid = new Optimum(start,end,theStr);
}
/**
* 比較并獲取最優(yōu)解
*/
Optimum finest = left;
if (mid!=null && mid.len>finest.len)
finest = mid;
if (right!=null && right.len>finest.len)
finest = right;
res = finest;
}
}
/**
* 講此子問(wèn)題的最優(yōu)解記錄到數(shù)組中
*/
solArr[start][end] = res;
/**
* 返回解
*/
return res;
}
}
class Optimum {
/**
* 此類(lèi)代表原始字符串的一個(gè)子串的最長(zhǎng)回文子串
* @param start 此回文串在原始字符串中的起始偏移量
* @param end 此回文串在原始字符串中的終止偏移量
* @param len 此回文串的長(zhǎng)度
* @param str 此回文串本身
*/
int start = 0;
int end = 0;
int len = -1;
String str = "";
@Override
public String toString() {
return "Solution{" +
"start=" + start +
", end=" + end +
", len=" + len +
", str='" + str + '\'' +
'}';
}
public Optimum() {
}
public Optimum(int start, int end, String oriStr) {
this.start = start;
this.end = end;
this.len = end-start+1;
this.str = oriStr.substring(start,end+1);
}
}到此，關(guān)于“如何編寫(xiě)代碼實(shí)現(xiàn)一個(gè)字符串的最長(zhǎng)回文子串”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！
