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"
1 class Solution { 2 public boolean isPalindromic(String s, int begin, int end) { 3 if (begin == end) 4 return true; 5 for (int i = 0; i <= (end - begin) / 2; i++) { 6 if (s.charAt(begin + i) != s.charAt(end - i)) 7 return false; 8 } 9 return true;10 }11 12 public String longestPalindrome(String s) {13 if (s.length() <= 1) return s;14 int[] res = new int[s.length()];// 存放以当前位置结束的最长回文子串的长度15 16 res[0] = 1;17 for (int i = 1; i < s.length(); i++) {18 int begin = i - res[i - 1] - 1;//以i-1位置结尾的最长回文子串的开始位置的前一个位置19 if (begin < 0) {20 /*21 * 查找以i结尾的最长回文子串22 * */23 for (int j = 0; j <= i; j++) {24 if (isPalindromic(s, j, i)) {25 res[i] = i - j + 1;26 break;27 }28 }29 } else {30 if (s.charAt(begin) == s.charAt(i)) {31 res[i] = res[i - 1] + 2;32 } else {33 // 判断begin+1到i子串是否是回文子串34 for (int j = 0; j <= i; j++) {35 if (isPalindromic(s, j, i)) {36 res[i] = i - j + 1;37 break;38 }39 }40 }41 }42 }43 int max = 0;44 for (int i = 0; i < s.length(); i++) {45 if (res[max] < res[i]) max = i;46 }47 return s.substring(max - res[max] + 1, max + 1);48 }49 }
动态规划解法：d[i][j]：表示子串(i,j)是否是回文子串
1 class Solution { 2 public String longestPalindrome(String s) { 3 if (s.length() <= 0) return s; 4 boolean[][] d = new boolean[s.length()][s.length()]; 5 int max = 0, begin = 0, end = 0; 6 for (int i = 0; i < s.length(); i++) { 7 d[i][i] = true; 8 } 9 for (int j = 1; j < s.length(); j++) {10 for (int i = 0; i < j; i++) {11 if (i == j - 1) {12 if (s.charAt(i) == s.charAt(j)) {13 d[i][j] = true;14 if (max < j - i) {15 begin = i;16 end = j;17 max = j - i;18 }19 } else {20 d[i][j] = false;21 }22 } else {23 if (d[i + 1][j - 1]) {24 if (s.charAt(i) == s.charAt(j)) {25 d[i][j] = true;26 if (max < j - i) {27 begin = i;28 end = j;29 max = j - i;30 }31 } else {32 d[i][j] = false;33 }34 } else {35 d[i][j] = false;36 }37 }38 }39 }40 return s.substring(begin, end+1);41 }42 } 第三种解法：由中间向两遍扩散查找回文串
1 class Solution { 2 public String longestPalindrome(String s) { 3 if (s.length() <= 1) return s; 4 int max = 0; 5 int low = 0, high = 0; 6 //计算奇数回文子串的长度 7 for (int i = 0; i < s.length(); i++) { 8 int begin = i, end = i; 9 while (begin > 0 && end < s.length() - 1) {10 --begin;11 ++end;12 if (s.charAt(begin) == s.charAt(end)) {13 if (max < end - begin) {14 max = end - begin;15 low = begin;16 high = end;17 }18 } else {19 break;20 }21 }22 }23 24 //计算偶数回文子串的长度25 for (int i = 0; i < s.length() - 1; i++) {26 int begin = i, end = i + 1;27 if (s.charAt(i) != s.charAt(i+1)) continue;28 else {29 if (max < end-begin){30 max=end-begin;31 low=begin;32 high=end;33 }34 }35 while (begin > 0 && end < s.length() - 1) {36 --begin;37 ++end;38 if (s.charAt(begin) == s.charAt(end)){39 if (max < end-begin){40 max=end-begin;41 low= begin;42 high=end;43 }44 }else {45 break;46 }47 }48 }49 return s.substring(low, high + 1);50 }51 }