5. Longest Palindromic Substring

APICloud 发布于2019-08-14 17:57 / 2670人阅读

摘要：暴力算法就是找到所有每个都进行的检查。时间复杂度是个调用平均时长为这里唯一确定用的是头尾表示。因为的对称性，我们可以从中间出发向两边延展，找到最长的分为两种基本情况。奇数长度出发点一致，都为偶数长度出发点为相邻的点，和结束是

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

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

暴力算法就是找到所有substring, 每个都进行isPalindrome的检查。时间复杂度是O(N^3). N^2个substring, 调用isPalindrome平均时长为O(N).
这里唯一确定substring用的是头尾(i,j)表示。因为palindrome的对称性，我们可以从中间出发向两边延展，找到最长的palindrome.
分为ABA, ABBA两种基本情况。一共有N个位置唯一标记点，调用一次extenPalindrome时间worst case是O(len)，
最大也就是中点位置的O(n/2). 总的时间复杂度大致为O(N^2/4)

另外还有一种方法，想法来自于palindrome partition那题。 用一个boolean[i,j]表示(i,j)是否为palindrome, 
比较i-1和j+1. 写过一个，代码复杂，跑起来特别慢，特别是"aaaaaaa"这种，所以抛弃掉。

public class Solution {
    private int lo = 0, maxLen = 0;
    
    public String longestPalindrome(String s) {
        if(s.isEmpty()) return null;
        int len = s.length();
        if(len < 2) return s;
        
        for(int i=0; i= 0 && k < s.length() && s.charAt(j) == s.charAt(k)){
            j--;
            k++;
        }
        // 结束是s(j)!=s(k)
        // k-1 - (j+1) +1 = k - j -1
        if(maxLen < k - j - 1){
            lo = j + 1;
            maxLen = k - j - 1;
        }
    }
}

GPU服务器私有云 Palindromic Longest Substring SUBSTRING_INDEX

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

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

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 最长回文子串

摘要：难度题目是说给出一个字符串求出这个字符串的最长回文的子串回文是指前后完全对称的字符串像是之类的都算是回文奇数字母的回文和偶数字母的回文中心是不一样的奇数字母比如的中心在中间字母上偶数字母比如的回文在中间两字母的中心上由此可见回文中心点实际上 Given a string s, find the longest palindromic substring in s. You may as...

NotFound 2019-08-14 17:12 评论0 收藏0
leetcode 5 Longest Palindromic Substring Java &

摘要：回文的意思就是反转字符串后和原字符串相等。因为这种想法没次都是两边同时扩展。所以要分目标字符串长度为奇数目标字符串为偶数两种情况。题目详情 Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.题目的意思是输入...

JessYanCoding 2019-08-15 14:27 评论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
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