5. Longest Palindromic Substring.md

5. Longest Palindromic Substring

Problem

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.

tag:

• string

Solution

java

	//动态规划
    public String longestPalindrome(String s) {
        if(s==null) return s;
        int len = s.length();
        String res = "";
        boolean[][] dp = new boolean[len][len];
        for(int i=len-1; i>=0; i--) {
            for(int j=i; j<len; j++) {
                dp[i][j] = (s.charAt(i)==s.charAt(j)) && (j-i<3 || dp[i+1][j-1]);
                if(dp[i][j]&&j-i+1>res.length()) res = s.substring(i,j+1);
            }
        }
        return res;
    }

go

//中心扩展法
func longestPalindrome(s string) string {
	start, maxlen := 0, 0
	for i, n := 0, len(s); i < n; i++ {
		if k, v := extend(s, i, i); v > maxlen {
			maxlen = v
			start = k
		}
		if k, v := extend(s, i, i+1); v > maxlen {
			maxlen = v
			start = k
		}
	}
	return s[start : start+maxlen]
}

func extend(s string, i, j int) (int, int) {
	for n := len(s); i >= 0 && j < n && s[i] == s[j]; i, j = i-1, j+1 {
	}
	return i + 1, j - i - 1
}