Leetcode 5 Longest Palindromic Substring 最长回文子串

NotFound 发布于2019-08-14 17:12 / 758人阅读

摘要：难度题目是说给出一个字符串求出这个字符串的最长回文的子串回文是指前后完全对称的字符串像是之类的都算是回文奇数字母的回文和偶数字母的回文中心是不一样的奇数字母比如的中心在中间字母上偶数字母比如的回文在中间两字母的中心上由此可见回文中心点实际上

Given a string s, find the longest palindromic substring in s. You may assume
that the maximum length of s is 1000.
Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example:
Input: "cbbd"
Output: "bb"

难度:Medium

题目是说, 给出一个字符串, 求出这个字符串的最长"回文"的子串. 回文是指前后完全对称的字符串, 像是abba cabac 之类的都算是回文.

奇数字母的回文和偶数字母的回文中心是不一样的, 奇数字母比如aba的中心在中间字母上, 偶数字母比如abba的回文在中间两字母的中心上, 由此可见, 回文中心点实际上最小间隔是"半个"字符. 我们可以考虑回文中心以半个字符间距不断移动, 去寻找最长回文子串.

public class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        int maxl = 0;
        int maxr = 0;
        int maxLen = 1;
        for (int k = 0; k < len * 2 - 1; k++) {
            int base = 0;
            int plen = 1;
            int left = k / 2;
            int right = k / 2;
            if (k % 2 == 1) {
                base = 1;
                plen = 0;
                left = (k - 1) / 2;
                right = (k + 1) / 2;
            }
            for (int i = base; k - i >= 0 && (k + i) / 2 <= len - 1; i = i + 2) {
                int l = (k - i) / 2;
                int r = (k + i) / 2;
                if (s.charAt(l) != s.charAt(r)) {
                    break;
                }
                left = l;
                right = r;
                plen = r - l + 1;
            }
            if (plen > maxLen) {
                maxl = left;
                maxr = right;
                maxLen = plen;
            }
        }
        return s.substring(maxl, maxr + 1);
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.longestPalindrome("a"));
        System.out.println(s.longestPalindrome("aba"));
        System.out.println(s.longestPalindrome("aa"));
        System.out.println(s.longestPalindrome("abac"));
        System.out.println(s.longestPalindrome("baab"));
    }
}

私有云服务器托管最长公共子串 java最长相同子串 Palindromic Longest

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66484.html

LeetCode.5 最长回文子串(longest-palindromic-substring)(J

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

Steven 2019-08-23 16:47 评论0 收藏0
LeetCode——Longest Palindromic Substring

摘要：题目即求最长回文子序列原题链接此篇博客仅为学习记录我的解法及代码暴力解决，用及进行两层遍历循环中套一层循环，用遍历，求最长回文序列字符串，同时用变量记录最长子序列这种写法很暴力，效率很低，一层循环，一层循环，回文序列对比一层，时间复杂度为辣题目： Given a string s, find the longest palindromic substring in s. You ma...

shevy 2019-08-23 18:26 评论0 收藏0
LeetCode-5 Longest Palindromic Substring

摘要：题目解析题目是要找出最长的回文字符串，拿到题目的第一反应是遍历子串，然后一直替换最长的子字符串即可了。但是这种解法遇到极端输入状况就会超时，指定的最长长度为，遍历子串需要两次循环，判断回文需要一次循环，所以总的效率为，那么极端状况会超时。题目 Given a string s, find the longest palindromic substring in s. You may ...

psychola 2019-08-16 13:53 评论0 收藏0
LeetCode代码分析——5. longest-palindromic-substring（动态规

摘要：题目描述给定一个字符串，找到中最长的回文子串。你可以假设的最大长度为。示例输入输出注意也是一个有效答案。示例输入输出思路分析暴力解法解决一个问题如果没有思路，就要想办法从简单粗暴的解法开始，然后想办法优化它。题目描述 https://leetcode-cn.com/probl... 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1： ...

neuSnail 2019-08-19 10:35 评论0 收藏0
[Leetcode] Longest Palindromic Substring 最长回文子字符串

摘要：这种解法中，外层循环遍历的是子字符串的中心点，内层循环则是从中心扩散，一旦不是回文就不再计算其他以此为中心的较大的字符串。 Longest Palindromic Substring Given a string S, find the longest palindromic substring in S. You may assume that the maximum length ...

KnewOne 2019-08-14 12:17 评论0 收藏0