题目描述

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

示例 1：

输入: "babad"

输出: "bab"

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

示例 2：

输入: "cbbd"

输出: "bb"

思路

本题运用了一些动态规划的思想，关于动态规划，可以看看我之前的一篇博客了解一下。

LeetCode 探索初级算法 - 动态规划

1、首先要找到最简情况。这道题中的最简情况就是一个字母（比如“a”）和一对字母（比如”bb“）。

2、根据最简情况向复杂拓展。更长的回文子串肯定是在简单的情况下增长而来的，如何增长呢？就是在上一个回文子串的基础上，左右各加一个同样的字母。

3、针对一个中心，不断向外拓展，直到遇到不是回文子串。

4、遍历字符串，对每一个字符使用一遍拓展检测，保存最长回文子串的长度，便于最后按索引取子串。

源码

public class LongestPalindromicSubstring {

    public String longestPalindrome (String s) {

        if (s == null || s.length() == 0) return "";

        int start = 0, end = 0;

        for (int i = 0; i < s.length(); i++) {

            int len1 = expandAroundCenter(s, i, i); // 一字母回文拓展

            int len2 = expandAroundCenter(s, i, i + 1); // 二字母回文拓展

            int len = Math.max(len1, len2);

            if (len > end - start) {

                start = i - (len - 1) / 2;

                end = i + len / 2;

            }

        }

        return s.substring(start, end + 1);

    }

    // 返回一个回文字串的长度

    private int expandAroundCenter (String s, int l, int r) {

        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {

            l--;

            r++;

        }

        return r - l - 1;

    }

    public static void main (String[] args) {

        LongestPalindromicSubstring lps = new LongestPalindromicSubstring();

        String s = "babad";

        System.out.println(lps.longestPalindrome(s));

    }

}

心得体会

1、从暴力破解方法入手，找到优化方法

2、字符串方法substring()的索引是左闭右开的

巴特西

【LeetCode】5# 最长回文子串

题目描述

思路

源码

心得体会

最新文章

热门文章