🌗 5. 最长回文子串

难度: 🌗

问题描述

---

解法 1 - 中心扩散

class Solution {
    public String longestPalindrome(String s) {
        // 思路：
        // method 1 - 中心扩散法
        int len = s.length();
        int count = 1;
        int[] res = new int[] {0, 0};
        for(int i = 0; i < len; i ++) {
            int[] cur = mySol(s, len, i);
            // System.out.println(i + "   " + Arrays.toString(cur));
            int tmp = cur[1] - cur[0] + 1;
            if(tmp > count) {
                res[0] = cur[0];
                res[1] = cur[1];
                count = tmp;
            }
        }
        return s.substring(res[0], res[1] + 1);
    }

    private int[] mySol(String s, int len, int index) {
        int[] res = new int[]{index, index};
        int count = 1;
        int left = index;
        int right = index;
        // index 为中点
        while(left >= 0 && right < len) {
            if(s.charAt(left) == s.charAt(right)) {
                left --;
                right ++;
            } else {
                break;
            }
        }
        // [left +1, right - 1] 区间有效
        if(right - 1 - left > count) {
            res[0] = left + 1;
            res[1] = right - 1;
            count = right - 1 - left;
        }
        // (index, index + 1) 为中点
        if(index + 1 < len && s.charAt(index) == s.charAt(index + 1)) {
            left = index;
            right = index + 1;
            while(left >= 0 && right < len) {
                if(s.charAt(left) == s.charAt(right)) {
                    left --;
                    right ++;
                } else {
                    break;
                }
            }
        }
        if(right - 1 - left > count) {
            res[0] = left + 1;
            res[1] = right - 1;
        }
        return res;
    }
}

---

输出 1

---

解法 2 - dp

class Solution {
    public String longestPalindrome(String s) {
        // 思路：
        // dp[i][j] = dp[i + 1][j - 1]
        int len = s.length();
        int count = 1;
        int[] res = new int[]{0, 0};
        // dp
        boolean[][] dp = new boolean[len][len];
        for(int i = len - 1; i >= 0; i --) {
            for(int j = i; j < len; j ++) {
                if(i == j) {
                    dp[i][j] = true;
                } else if(i == j - 1) {
                    if(s.charAt(i) == s.charAt(j)) {
                        dp[i][j] = true;
                        if(j - i + 1 > count) {
                            count = j - i + 1;
                            res[0] = i;
                            res[1] = j;
                        }
                    }
                } else {
                    if(dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j)) {
                        dp[i][j] = true;
                        if(j - i + 1 > count) {
                            count = j - i + 1;
                            res[0] = i;
                            res[1] = j;
                        }
                    }
                }
            }
        }
        return s.substring(res[0], res[1] + 1);
    }
}

---

输出 2