[2018-Interview] Longest Palindromic Substring

Original question: https://leetcode.com/problems/longest-palindromic-substring/description/

My answer:

Used answer from Jiuzhang as reference:

https://www.jiuzhang.com/solutions/longest-palindromic-substring/

Answer 1: DP solution

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }
        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];
        for (int i = 0; i < n; i ++) {
            isPalindrome[i][i] = true;
        }

        int maxLength = 1;
        int start = 0;
        
        for (int i = n - 2; i >= 0; i --) {
            isPalindrome[i][i + 1] = s.charAt(i) == s.charAt( i + 1);
            if (isPalindrome[i][i + 1] ) {
                start = i;
                maxLength = 2;
            }
        }

        for (int i = n - 1; i >= 0; i --) {// start from end; 
            // otherwise, if start from beginning, there won't be [i+1][j-1] for reference
            for (int j = i + 2; j < n; j ++) {
                isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && (s.charAt(i) == s.charAt(j));
                if (isPalindrome[i][j]) {
                    if (j - i + 1 > maxLength) {
                        maxLength = j - i + 1;
                        start = i;
                    }
                }
            }
        }
        return s.substring(start, start + maxLength);
    }
}

Answer 2: try to find the longest palindrome with each point as center point

/**
* 本参考程序来自九章算法，由 @令狐冲 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
*/ 

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        
        int start = 0, len = 0, longest = 0;
        for (int i = 0; i < s.length(); i++) {
            len = findLongestPalindromeFrom(s, i, i);
            if (len > longest) {
                longest = len;
                start = i - len / 2;
            }
            
            len = findLongestPalindromeFrom(s, i, i + 1);
            if (len > longest) {
                longest = len;
                start = i - len / 2 + 1;
            }
        }
        
        return s.substring(start, start + longest);
    }
    
    private int findLongestPalindromeFrom(String s, int left, int right) {
        int len = 0;
        while (left >= 0 && right < s.length()) {
            if (s.charAt(left) != s.charAt(right)) {
                break;
            }
            len += left == right ? 1 : 2;
            left--;
            right++;
        }
        
        return len;
    }
}