Longest Palindromic Substring
简介:字符串中最长的回文字符串
回文字符串:中心对称的字符串 ,如 mom，noon
问题详解：
给定一个字符串s,寻找字符串中最长的回文字符串,假设字符串s长度最长为1000.
举例：
1:
输入: “babad”
输出: “bab”
注: “aba” 也是一种答案.
2:
输入: “cbbd”
输出: “bb”
官方实现 : Expand Around Center
我们可以从字符串中心寻找回文字符串,例如"aba"的中心为’b’,"baab"的中心为两个a中间,所以分两种情况考虑,一种是中心为i,另一种是i和i+1,这里我们需要注意的是String里的方法substring(index start,index end),第二个s是小写的,并且是从start开始一直到end结尾但不包含end索引处的字符,所以我们要end+1
复杂度分析
时间复杂度分析 : O(n^2).
空间复杂度 : O(1).
小白刷题之路,请多指教— — 要么大器晚成,要么石沉大海

Java基础算法之找出一段字符串中所有回文串、最长的回文串以及最长回文串长度



回文的含义是：字符串从左向右看和从右向左看是相同的，例如：abba，1234321。
单一字符亦是回文串


package com.zhaowl.interview.base;

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 获取最长回文串
 * 回文的含义是：子串从左向右看和从右向左看是相同的，例如：abba，1234321。
 * 注意：单一字符亦是回文串
 *
 * @author : Create by 半路勇者 at 2020/11/24 16:03
 */
@Slf4j
public class LongestPalindromicSubstring {

    /**
     * 判断字符串是否是回文串
     *
     * @param string 字符串
     * @return 是否是回文串
     */
    public static boolean isPalindromic(String string) {
        return string.equalsIgnoreCase(new StringBuffer(string).reverse().toString());
        // 用如下方法判断是否是回文串，则会忽略掉单一字符
        /*int length = string.length();
        boolean bool = false;
        for (int i = 0; i < length / 2; i++) {
            bool = (string.charAt(i) == string.charAt(length - i - 1));
            if (!bool) {
                break;
            }
        }
        return bool;*/
    }

    /**
     * 一段一段的截取，判断是否是回文串
     *
     * @param string 字符串
     * @return 最长回文串以及长度
     */
    public static Map<String, Object> getLongestPalindromic(String string) {
        Map<String, Object> map = new HashMap<>();
        // 所有回文串集合
        List<String> strings = new ArrayList<>();
        // 如果字符串为空，返回空
        if (string == null || string.equals("") || string.length() == 0) {
            return null;
        }
        // 保存最长回文串
        String maxStr = null;
        // 保存回文串长度
        int length = 0;
        // 保存最长回文串长度
        int maxLength = 0;
        for (int i = 0; i < string.length(); i++) {
            /*
             * 这里之所以设置j <= string.length()，是避免字符串本身就是一个回文串，原因如下
             * substring(beginIndex, endIndex)
             * endIndex：输入的数值减1
             */
            for (int j = i + 1; j <= string.length(); j++) {
                String sub = string.substring(i, j);
                // 找到回文串则缓存该串长度，用于比较
                if (isPalindromic(sub)) {
                    strings.add(sub);
                    length = sub.length();
                }
                // 如果该串长度大于上一个回文串，则最大长度设置为当前回文串长度，并缓存当前回文串为最大长度回文串
                if (length > maxLength) {
                    maxLength = length;
                    maxStr = sub;
                }
                // 回文串长度初始化为0，并进行下一次循环截取
                length = 0;
            }
        }
        map.put("maxLength", maxLength);
        map.put("maxStr", maxStr);
        map.put("strings", strings);
        return map;
    }

    public static void main(String[] args) {
        String string = "1234321";
        Map<String, Object> map = getLongestPalindromic(string);
        // 7
        log.info("最长回文串长度：" + map.get("maxLength"));
        // 1234321
        log.info("最长回文字符串：" + map.get("maxStr"));
        // [1, 1234321, 2, 23432, 3, 343, 4, 3, 2, 1]
        log.info("所有回文串：" + map.get("strings"));
    }

}

题目
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2：
输入: “cbbd”
输出: “bb”

题目：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: “babad”

输出: “bab”

注意: “aba” 也是一个有效答案。

示例 2：

输入: “cbbd”

输出: “bb”
思路：中心扩散法——遍历每一个索引，以这个索引为中心，利用“回文串”中心对称的特点，往两边扩散，看最多能扩散多远。

在这里需要注意一个细节：回文串在长度为奇数和偶数的时候，“回文中心”的形式是不一样的。

1、奇数回文串的“中心”是一个具体的字符，例如：回文串“aba”的中心是字符“b”；

2、偶数回文串的“中心”是位于中间的那两个字符，如：回文串“abba”的中心是两个“bb”；

Python解法：
class Solution:
    def longestPalindrome(self, s: str) -> str:
        size = len(s)
        if size < 2:
            return s

        # 至少是 1
        max_len = 1
        res = s[0]

        for i in range(size):
            palindrome_odd, odd_len = self.__center_spread(s, size, i, i)
            palindrome_even, even_len = self.__center_spread(s, size, i, i + 1)

            # 当前找到的最长回文子串
            cur_max_sub = palindrome_odd if odd_len >= even_len else palindrome_even
            if len(cur_max_sub) > max_len:
                max_len = len(cur_max_sub)
                res = cur_max_sub

        return res

    def __center_spread(self, s, size, left, right):
        """
        left = right 的时候，此时回文中心是一个字符，回文串的长度是奇数
        right = left + 1 的时候，此时回文中心是一个空隙，回文串的长度是偶数
        """
        i = left
        j = right

        while i >= 0 and j < size and s[i] == s[j]:
            i -= 1
            j += 1
        return s[i + 1:j], j - i - 1

java解法：
public class Solution {

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }
        int maxLen = 1;
        String res = s.substring(0, 1);
        // 中心位置枚举到 len - 2 即可
        for (int i = 0; i < len - 1; i++) {
            String oddStr = centerSpread(s, i, i);
            String evenStr = centerSpread(s, i, i + 1);
            String maxLenStr = oddStr.length() > evenStr.length() ? oddStr : evenStr;
            if (maxLenStr.length() > maxLen) {
                maxLen = maxLenStr.length();
                res = maxLenStr;
            }
        }
        return res;
    }

    private String centerSpread(String s, int left, int right) {
        // left = right 的时候，此时回文中心是一个字符，回文串的长度是奇数
        // right = left + 1 的时候，此时回文中心是一个空隙，回文串的长度是偶数
        int len = s.length();
        int i = left;
        int j = right;
        while (i >= 0 && j < len) {
            if (s.charAt(i) == s.charAt(j)) {
                i--;
                j++;
            } else {
                break;
            }
        }
        // 这里要小心，跳出 while 循环时，恰好满足 s.charAt(i) != s.charAt(j)，因此不能取 i，不能取 j
        return s.substring(i + 1, j);
    }
}