LeetCode：5.最长回文子串

思路一：动态规划

状态空间设置：设p(i, j)为字符串的下标i到j的子串，包含i和j；如果是回文串，则p(i, j)==true

则有：p(i, j)的递推方程为

当p(i, j)长度为1时： p(i, j) = p(i, i) = true

当p(i, j)长度为2时：p(i, j) = p(i, i+1) = (S[i]==s[j])

当p(i, j)长度大于2时：p(i, j) = ( p(i+1, j-1) && (s[i]==s[j]) )

由上面的状态空间表达式和递推方程，可以写出如下代码解法：

public class Test5 {

	@Test
	public void test() {
		System.out.println(longestPalindrome("12324"));
	}
	
	public String longestPalindrome(String s) {
		
		if(s==null || s.length()==0) {
			return "";
		}
		
		boolean[][] dp = new boolean[s.length()][s.length()];
		String ans = "";
		
		for(int length=1; length<s.length()+1; length++) {
			for(int i=0; i<s.length()-length+1; i++) {
				if(length==1) {
					dp[i][i] = true;
				} else if(length==2) {
					dp[i][i+1] = (s.charAt(i)==s.charAt(i+1));
				} else {
					dp[i][i+length-1] = dp[i+1][i+length-2] & (s.charAt(i)==s.charAt(i+length-1));
				}
				
				if((ans.length()<length) && dp[i][i+length-1]) {
					ans = s.substring(i, i+length);
				}
			}
			
		}
		
		return ans;
	}
}