5. Longest Palindromic Substring

DP

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        int startIndex = 0, endIndex = 0;

        // 定义 dp[i][j] 为字符串 s[i, j] 是否为回文字符串，潜在条件 j >= i, dp[i][j] 可由 dp[i + 1][j - 1] 转移而来
        boolean[][] dp = new boolean[n][n];

        for (int i = n - 1; i >= 0; i--) {
            // 单个字符肯定为回文字符串，无需计算 i == j 时的状态
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    // 判断 dp[i + 1][j - 1] 是否是回文字符串
                    if (i + 1 >= j - 1) {
                        // 此处同时处理了奇偶字符串的情况
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }

                    if (dp[i][j]) {
                        if (j - i + 1 > endIndex - startIndex + 1) {
                            startIndex = i;
                            endIndex = j;
                        }
                    }
                }
            }
        }

        return s.substring(startIndex, endIndex + 1);
    }
}

Diffusion

class Solution {

    private static class IndexHolder {
        private int startIndex;
        private int endIndex;
    }

    public String longestPalindrome(String s) {
        IndexHolder indexHolder = new IndexHolder();

        for (int i = 0; i < s.length() - 1; i++) {
            tryExpand(s, i, i, indexHolder);
            tryExpand(s, i, i + 1, indexHolder);
        }

        return s.substring(indexHolder.startIndex, indexHolder.endIndex + 1);
    }

    private void tryExpand(String s, int i, int j, IndexHolder indexHolder) {
        while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            i--;
            j++;
        }

        if ((j - 1) - (i + 1) + 1  > indexHolder.endIndex - indexHolder.startIndex + 1) {
            // 注意是将 i + 1 与 j - 1 记录下来，因为 i 与 j 此时指向的字符已经不相等
            indexHolder.startIndex = i + 1;
            indexHolder.endIndex = j - 1;
        }
    }
}

Reference

5. Longest Palindromic Substring