LeetCode-5 Longest Palindromic Substring

psychola 发布于2019-08-16 13:53 / 3108人阅读

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

题目

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"

解析

题目是要找出最长的回文字符串，拿到题目的第一反应是遍历子串，然后一直替换最长的子字符串即可了。
但是这种解法遇到极端输入状况就会超时，指定的最长长度为1000，遍历子串需要两次循环，判断回文需要一次循环，所以总的效率为O(n^3)，那么极端状况会超时。

超时解法

    public String longestPalindrome(String s) {
        String longestStr = "";
        for(int start = 0 ; start= temp.length()){
                    continue;
                }
                if(checkStrValid(temp) && temp.length()>longestStr.length()){
                    longestStr = temp;
                }
            }
        }
        return longestStr;
    }
    private boolean checkStrValid(String s){
        if(s==null || s.length()==0){
            return false;
        }
        int start = 0 ,end = s.length()-1;
        while(start < end){
            if(s.charAt(start++)!=s.charAt(end--)){
                return false;
            }
        }
        return true;
    }

正确解法

     public String longestPalindrome2(String s) {
        // parameter[0]保存start的值，parameter[1]保存maxLen的值
        // 这样定义变量是为了实现java引用传递
        int[] parameter = new int[2];
        for(int i = 0 ; i < s.length() ; ++i){
            // 如果是奇数回文字符串，例如aba,bab,bbabb等
            searchPalindrome(s , i , i ,parameter);
            // 如果是偶数回文字符串，例如bbbb,baab,ceddec等
            searchPalindrome(s , i , i+1 , parameter);
        }
        // 等价于s.subString(start , start + maxLen)
        return s.substring(parameter[0],parameter[0] + parameter[1]);
    }

    private void searchPalindrome(String s , int left , int right , int[] parameter){
        // 寻找回文字符串
        while(left>=0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            --left;
            ++right;
        }
        // 如果maxLen < 构造的回文子字符串长度
        if(parameter[1] < right - left - 1){
            // start = left + 1
            parameter[0] = left + 1;
            // maxLen = right - left - 1
            parameter[1] = right - left - 1 ;
        }
    }

定义int[] parameter的原因是为了支持函数引用传递，以免在searchPalindrome改变int参数值回到longestPalindrome2方法中值又回到原来的值，这是java方法参数值传递特性导致的。该方法效率为O(n^2)。

其他解法

还有一些比较巧妙的解法例如动态规划，马拉车算法等，目前还不能理解其中的精髓，等到我学会本质之后再补充，先贴个大神的博客放着。
https://www.cnblogs.com/grand...

云服务器 GPU云服务器 Palindromic Longest Substring SUBSTRING_INDEX

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

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

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

摘要：这种解法中，外层循环遍历的是子字符串的中心点，内层循环则是从中心扩散，一旦不是回文就不再计算其他以此为中心的较大的字符串。 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
5. Longest Palindromic Substring

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

APICloud 2019-08-14 17:57 评论0 收藏0