5. Longest Palindromic Substring

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    private static class Result {
        private int maxLength = 1;
        private int startIndex;
    }

    public String longestPalindrome(String s) {
        Result result = new Result();

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

        return s.substring(result.startIndex, result.startIndex + result.maxLength);
    }

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

        // now: s[i] != s[j]
        int length = (j - 1) - (i + 1) + 1;
        if (length > result.maxLength) {
            result.maxLength = length;
            result.startIndex = i + 1; // 注意起点为 i + 1
        }
    }
}

Diffusion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public String longestPalindrome(String s) {
        int startIndex = 0, maxLength = 1;
        for (int i = 0; i < s.length() - 1; i++) {
            int length = Math.max(tryExpand(s, i, i), tryExpand(s, i, i + 1));
            if (length > maxLength) {
                maxLength = length;
                startIndex = i - (length + 1) / 2 + 1; // 注意 i 是中点，所以需要计算 startIndex
            }
        }

        return s.substring(startIndex, startIndex + maxLength);
    }

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

        // now: s[i] != s[j]
        return j - i - 1;
    }
}

References

5. Longest Palindromic Substring