当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.005.LongestPalindromicSubstring 最长回文子串

LeetCode.005.LongestPalindromicSubstring 最长回文子串

题目描述

005 Longest Palindromic Substring
https://leetcode-cn.com/problems/longest-palindromic-substring/

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"

Note: “aba” is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

解题过程

这道题面试被问过,不会做。
这次先自己绞尽脑汁想了想,一开始想着搞个滑动窗口O(n)遍历解决,发现行不通,回文子串的子串不一定回文。
只好看了看题解,中心扩展法 很好理解,自己实现了一下,O(n^2) 复杂度,很好写。 Manacher 马拉车算法是中心扩展法的升级,将复杂度降到了O(n),没仔细看。

package _005_LongestPalindromicSubstring;

/**
 * @author madaimeng.com
 */
public class LongestPalindromicSubstringV2019 {
    private static class Solution {
        public String longestPalindrome(String s) {
            String result = "";
            for (int i = 0; i < s.length(); i++) {
                String extend1 = extend(s, i, i);
                result = extend1.length() > result.length() ? extend1 : result;
                if (i + 1 < s.length()) {
                    String extend2 = extend(s, i, i + 1);
                    result = extend2.length() > result.length() ? extend2 : result;
                }
            }
            return result;
        }

        public String extend(String s, int pivot1, int pivot2) {
            while (pivot1 >= 0 && pivot2 < s.length() && s.charAt(pivot1) == s.charAt(pivot2)) {
                pivot1--;
                pivot2++;
            }
            return s.substring(pivot1+1, pivot2);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.longestPalindrome("babad"));
        System.out.println(solution.longestPalindrome("cbbd"));
        System.out.println(solution.longestPalindrome("cabcba"));
        System.out.println(solution.longestPalindrome("bb"));
        System.out.println(solution.longestPalindrome("a"));
        System.out.println(solution.longestPalindrome(""));
    }
}

GitHub代码

leetcode-java/problems/_005_LongestPalindromicSubstring/
https://github.com/masikkk/leetcode-java/tree/master/problems/_005_LongestPalindromicSubstring


上一篇 北京中医药大学第三医院看颈椎记录

下一篇 OpenResty

阅读
评论
330
阅读预计2分钟
创建日期 2019-11-22
修改日期 2019-11-26
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:

评论