---

---

暴力法

---

---

動(dòng)態(tài)規(guī)劃解法

---

class Solution {public String longestPalindrome(String s) {if (s == null) return null;char[] cs = s.toCharArray();if (cs.length <= 1) return s;// 最長(zhǎng)回文子串的長(zhǎng)度（至少是1）int maxLen = 1;// 最長(zhǎng)回文子串的開(kāi)始索引int begin = 0;boolean[][] dp = new boolean[cs.length][cs.length];// 從下到上（i由大到小）for (int i = cs.length - 1; i >= 0; i--) {// 從左到右（j由小到大）for (int j = i; j < cs.length; j++) {// cs[i, j]的長(zhǎng)度int len = j - i + 1;dp[i][j] = (cs[i] == cs[j]) && (len <= 2 || dp[i + 1][j - 1]);if (dp[i][j] && len > maxLen) { // 說(shuō)明cs[i, j]是回文子串maxLen = len;begin = i;}}}return new String(cs, begin, maxLen);} }

---

---

擴(kuò)展中心法

??

class Solution {public String longestPalindrome(String s) {if (s == null) return null;char[] cs = s.toCharArray();if (cs.length <= 1) return s;// 最長(zhǎng)回文子串的長(zhǎng)度（至少是1）int maxLen = 1;// 最長(zhǎng)回文子串的開(kāi)始索引int begin = 0;//掃描的范圍 [1,cs.length - 2] 從右往左掃 cs.length - 2 --->> 1for (int i = cs.length - 2; i >= 1; i--) {// 以字符為中心向左右擴(kuò)展int len1 = palindromeLength(cs, i - 1, i + 1);// 以字符右邊的間隙為中心向左右擴(kuò)展int len2 = palindromeLength(cs, i, i + 1);len1 = Math.max(len1, len2);if (len1 > maxLen) {maxLen = len1;begin = i - ((maxLen - 1) >> 1);}}// 以0號(hào)字符右邊的間隙為中心的最長(zhǎng)回文子串長(zhǎng)度是2if (cs[0] == cs[1] && maxLen < 2) {// cs[0, 1]就是最長(zhǎng)的回文子串begin = 0;maxLen = 2;}return new String(cs, begin, maxLen);}/*** @return 從l開(kāi)始向左、從r開(kāi)始向右掃描，獲得的最長(zhǎng)回文子串的長(zhǎng)度*/private int palindromeLength(char[] cs, int l, int r) {while (l >= 0 && r < cs.length && cs[l] == cs[r]) {l--;r++;}return r - l - 1;} }

?

總結(jié)

以上是生活随笔為你收集整理的5. 最长回文子串——暴力法---动态规划解法---扩展中心法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。