首页 > 代码库 > [LeetCode#5]Longest Palindromic Substring
[LeetCode#5]Longest Palindromic Substring
The problem: (The code of dynamic programming is very concise and elegant. You must learn it!)
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
My analysis:
The problem could be perfectly solved by using dynamic programming.
The state transformaion equation is clear, and could be divided into following kinds :
assume: p[i][j] indicate whether the string from position i to position j is a palindromic.
we could have following state transistion fuction:
1. p[i][j] == true; iff i = j
2. p[i][j] = s[i] == s[j]; iff j = i+1
3. p[i][j] = s[i][j] && p[i+1][j-1]; iff j > i + 1
My solution:
/*The state trasition at here:p[i][j] == true; iff i = jp[i][j] = s[i] == s[j]; iff j = i+1 p[i][j] = s[i][j] && p[i+1][j-1]; iff j > i + 1 */public class Solution { public String longestPalindrome(String s) { if (s.length() == 0 || s.length() == 1) return s; char[] s_Array = s.toCharArray(); int len = s.length(); int max_len = 0; int max_front = 0; int max_end = 0; boolean[][] pa_matrix = new boolean[len][len]; //the initial value of boolean type is false for (int i = 0; i < len; i++) { //note: i is the index for end, j is the index for front for (int j = 0; j <= i; j++) { //compute and memorize the pa_matrix from the bottom to up if (i == j) pa_matrix[i][j] = true; if ((i == j + 1) && (s_Array[i] == s_Array[j])) pa_matrix[i][j] = true; if ((i > j + 1) && pa_matrix[i - 1][j + 1] && (s_Array[i] == s_Array[j])) //don‘t miss condition pa_matrix[i][j] = true; if ((pa_matrix[i][j] == true) && (i - j + 1 > max_len)) { max_len = i - j + 1; max_front = j; max_end = i; } } } return s.substring(max_front, max_end + 1); //take care of the usage of String.subString ... index }}
[LeetCode#5]Longest Palindromic Substring