☆打卡算法☆LeetCode 214. 最短回文串 算法解析

示例 1：
输入： s = "aacecaaa"
输出： "aaacecaaa"

示例 2：
输入： s = "abcd"
输出： "dcbabcd"

class Solution {
    public String shortestPalindrome(String s) {
        char[] arr = s.toCharArray();
        int n = arr.length;
        if(n == 0) {
            return "";
        }
        int max = -1;
        for(int i = 0; i < (n + 1) / 2; ++i) {
            int len1 = expand(arr, i, i);
            int len2 = expand(arr, i, i + 1);
            int len = Math.max(len1, len2);
            // 回文串的长度刚好可以到达左边界 0
            if(i - (len - 1) / 2 == 0) {
                max = Math.max(max, len);
            }
        }
        String last = s.substring(max);
        return new StringBuilder(last).reverse() + s.substring(0, max) + last;
        
    }
    // 中心扩展
    public int expand(char[] arr, int l, int r) {
        while(l >= 0 &amp;&amp; r < arr.length &amp;&amp; arr[l] == arr[r]) {
            l--; r++;
        }
        return r - l - 1;
    }
}