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;
	}
}