5. 最长回文子串：

给你一个字符串 s，找到 s 中最长的回文子串。

样例 1：

 输入：
     s = "babad"
     
输出：
    "bab"
    
解释：
    "aba" 同样是符合题意的答案。

样例 2：

输入：
    s = "cbbd"
    
输出：
    "bb"

样例 3：

输入：
    s = "a"
    
输出：
    "a"

样例 4：

输入：
    s = "ac"
    
输出：
    "a"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母（大写 和 / 或 小写）组成

分析：

• 面对这道算法题目，二当家的陷入了沉思。
• 判断回文，一般就是双指针从两侧向中心移动判断。
• 但是这里如果还是用这种方式效率就会很低。
• 可以考虑判断每个字符作为中心时候，双指针向两侧移动，直到字符不同，就是该字符作为中心的最长回文。
• 另外对于长的回文，在其右臂的字符上找回文子串时可以利用左臂缓存加速，因为右臂与左臂对称。

题解：

rust

impl Solution {
    pub fn longest_palindrome(s: String) -> String {
        fn expand(s: &Vec<char>, left: usize, mut right: usize) -> usize {
            // 强转了i32是为了可以出负数
            let mut left = left as i32;
            while left >= 0 && right < s.len() && s[left as usize] == s[right] {
                left -= 1;
                right += 1;
            }
            return ((right as i32 - left - 2) >> 1) as usize;
        }

        let mut ns = Vec::with_capacity((s.len() << 1) + 1);
        ns.push('#');
        s.chars().for_each(|x| {
            ns.push(x);
            ns.push('#');
        });

        // 最终结果的头尾下标
        let (mut start, mut end) = (0, 0);
        // 臂长缓存
        let mut arm_len = vec![0usize; ns.len()];
        // 之前回文串的右边界,之前回文串的中位下标
        let (mut right, mut mid) = (0, 0);
        for i in 0..ns.len() {
            // 判断是否有过臂长缓存
            let min_arm_len;
            if i < right {
                // 缓存范围内
                min_arm_len = arm_len[(mid << 1) - i].min(right - i);
            } else {
                min_arm_len = 0;
            }
            // 当前臂长
            let cur_arm_len = expand(&ns, i - min_arm_len, i + min_arm_len);

            // 将当前臂长缓存
            arm_len[i] = cur_arm_len;

            // 新的串超出之前子串的范围，用新的范围覆盖
            if i + cur_arm_len > right {
                mid = i;
                right = i + cur_arm_len;
            }

            // 当前结果大于之前的结果
            if (cur_arm_len << 1) + 1 > end - start {
                start = i - cur_arm_len;
                end = i + cur_arm_len;
            }

            // 如果后面的剩下的字符不够最大臂长就没必要进行下去了
            if i + ((end - start) >> 1) >= ns.len() {
                break;
            }
        }

        return String::from(&s[start >> 1..end >> 1]);
    }
}

go

func longestPalindrome(s string) string {
    min := func(a int, b int) int {
        if a < b {
            return a
        }
        return b
    }

    expand := func(s []uint8, left int, right int) int {
        for left >= 0 && right < len(s) && s[left] == s[right] {
            left--
            right++
        }
        return (right - left - 2) >> 1
    }

    // 在字符之间加入#号，使得字符数恒定变为奇数
    ns := make([]uint8, len(s)<<1+1)
    ns[0] = '#'
    for i := 0; i < len(s); i++ {
        ns[(i<<1)+1] = s[i]
        ns[(i+1)<<1] = '#'
    }

    // 最终结果的头尾下标
    start, end := 0, 0

    // 臂长缓存
    armLen := make([]int, len(ns))
    // 之前回文串的右边界,之前回文串的中位下标
    right, mid := 0, 0
    for i := 0; i < len(ns); i++ {
        // 判断是否有过臂长缓存
        var minArmLen int
        if right > i {
            minArmLen = min(armLen[(mid<<1)-i], right-i)
        } else {
            minArmLen = 0
        }
        // 当前臂长
        curArmLen := expand(ns, i-minArmLen, i+minArmLen)

        // 将当前臂长缓存
        armLen[i] = curArmLen

        // 新的串超出之前子串的范围，用新的范围覆盖
        if i+curArmLen > right {
            mid = i
            right = i + curArmLen
        }

        // 当前结果大于之前的结果
        if (curArmLen<<1)+1 > end-start {
            start = i - curArmLen
            end = i + curArmLen
        }

        // 如果后面的剩下的字符不够最大臂长就没必要进行下去了
        if i+((end-start)>>1) >= len(ns) {
            break
        }
    }

    return string(s[start>>1 : end>>1])
}

c++

class Solution {
private:
    int expand(string s, int left, int right) {
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            --left;
            ++right;
        }
        return (right - left - 2) >> 1;
    }
public:
    string longestPalindrome(string s) {
        // 在字符之间加入#号，使得字符数恒定变为奇数
        string ns = "#";
        for (char c: s) {
            ns += c;
            ns += "#";
        }

        // 最终结果的头尾下标
        int start = 0, end = 0;

        // 臂长缓存
        int armLen[ns.length()];
        memset(armLen, 0, sizeof(int) * ns.length());
        // 之前回文串的右边界,之前回文串的中位下标
        int right = 0, mid = 0;
        for (int i = 0; i < ns.length(); ++i) {
            // 判断是否有过臂长缓存
            int minArmLen;
            if (right > i) {
                minArmLen = min(armLen[(mid << 1) - i], right - i);
            } else {
                minArmLen = 0;
            }
            // 当前臂长
            int curArmLen = expand(ns, i - minArmLen, i + minArmLen);

            // 将当前臂长缓存
            armLen[i] = curArmLen;

            // 新的串超出之前子串的范围，用新的范围覆盖
            if (i + curArmLen > right) {
                mid = i;
                right = i + curArmLen;
            }

            // 当前结果大于之前的结果
            if ((curArmLen << 1) + 1 > end - start) {
                start = i - curArmLen;
                end = i + curArmLen;
            }

            // 如果后面的剩下的字符不够最大臂长就没必要进行下去了
            if (i + ((end - start) >> 1) >= ns.length()) {
                break;
            }
        }

        return s.substr(start >> 1, (end - start) >> 1);
    }
};

c

int expand(char *s, int l, int left, int right) {
    while (left >= 0 && right < l && s[left] == s[right]) {
        --left;
        ++right;
    }
    return (right - left - 2) >> 1;
}

char *longestPalindrome(char *s) {
    const int l = strlen(s);
    const int nsl = (l << 1) + 1;
    char ns[nsl];
    ns[0] = '#';
    for (int i = 0; i < l; ++i) {
        ns[(i << 1) + 1] = s[i];
        ns[(i + 1) << 1] = '#';
    }

    // 最终结果的头尾下标
    int start = 0, end = 0;

    // 臂长缓存
    int armLen[nsl];
    memset(armLen, 0, sizeof(int) * nsl);
    // 之前回文串的右边界,之前回文串的中位下标
    int right = 0, mid = 0;
    for (int i = 0; i < nsl; ++i) {
        // 判断是否有过臂长缓存
        int minArmLen;
        if (right > i) {
            minArmLen = fmin(armLen[(mid << 1) - i], right - i);
        } else {
            minArmLen = 0;
        }
        // 当前臂长
        int curArmLen = expand(ns, nsl, i - minArmLen, i + minArmLen);

        // 将当前臂长缓存
        armLen[i] = curArmLen;

        // 新的串超出之前子串的范围，用新的范围覆盖
        if (i + curArmLen > right) {
            mid = i;
            right = i + curArmLen;
        }

        // 当前结果大于之前的结果
        if ((curArmLen << 1) + 1 > end - start) {
            start = i - curArmLen;
            end = i + curArmLen;
        }

        // 如果后面的剩下的字符不够最大臂长就没必要进行下去了
        if (i + ((end - start) >> 1) >= nsl) {
            break;
        }
    }

    s[end >> 1] = 0;

    return s + (start >> 1);
}

python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(s: str, left: int, right: int) -> int:
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return (right - left - 2) >> 1

        # 在字符之间加入 # 号，使得字符数恒定变为奇数
        ns = "#"
        for i in range(len(s)):
            ns += s[i]
            ns += '#'
        # 最终结果的头尾下标
        start, end = 0, 0
        # 臂长缓存
        armLen = [0] * len(ns)
        # 之前回文串的右边界, 之前回文串的中位下标
        right, mid = 0, 0
        for i in range(len(ns)):
            # 判断是否有过臂长缓存
            minArmLen = 0
            if right > i:
                minArmLen = min(armLen[(mid << 1) - i], right - i)
            # 当前臂长
            curArmLen = expand(ns, i - minArmLen, i + minArmLen)
            # 将当前臂长缓存
            armLen[i] = curArmLen
            # 新的串超出之前子串的范围，用新的范围覆盖
            if i + curArmLen > right:
                mid = i
                right = i + curArmLen
            # 当前结果大于之前的结果
            if (curArmLen << 1) + 1 > end - start:
                start = i - curArmLen
                end = i + curArmLen
            # 如果后面的剩下的字符不够最大臂长就没必要进行下去了
            if i + ((end - start) >> 1) >= len(ns):
                break
        return s[start >> 1: end >> 1]

java

class Solution {
     public String longestPalindrome(String s) {
        // 在字符之间加入#号，使得字符数恒定变为奇数
        char[] ns = new char[(s.length() << 1) + 1];
        ns[0] = '#';
        for (int i = 0; i < s.length(); ++i) {
            ns[(i << 1) + 1] = s.charAt(i);
            ns[(i + 1) << 1] = '#';
        }

        // 最终结果的头尾下标
        int start = 0, end = 0;

        // 臂长缓存
        int[] armLen = new int[ns.length];
        // 之前回文串的右边界,之前回文串的中位下标
        int right = 0, mid = 0;
        for (int i = 0; i < ns.length; ++i) {
            // 判断是否有过臂长缓存
            int minArmLen;
            if (right > i) {
                minArmLen = Math.min(armLen[(mid << 1) - i], right - i);
            } else {
                minArmLen = 0;
            }
            // 当前臂长
            int curArmLen = expand(ns, i - minArmLen, i + minArmLen);

            // 将当前臂长缓存
            armLen[i] = curArmLen;

            // 新的串超出之前子串的范围，用新的范围覆盖
            if (i + curArmLen > right) {
                mid = i;
                right = i + curArmLen;
            }

            // 当前结果大于之前的结果
            if ((curArmLen << 1) + 1 > end - start) {
                start = i - curArmLen;
                end = i + curArmLen;
            }

            // 如果后面的剩下的字符不够最大臂长就没必要进行下去了
            if (i + ((end - start) >> 1) >= ns.length) {
                break;
            }
        }

        return s.substring(start >> 1, end >> 1);
    }

    private int expand(char[] s, int left, int right) {
        while (left >= 0 && right < s.length && s[left] == s[right]) {
            --left;
            ++right;
        }
        return (right - left - 2) >> 1;
    }
}

非常感谢你阅读本文~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~