leetcode5 Longest Palindromic Substring 最长且为回数的子字符

Imfan 发布于2019-08-14 18:01 / 254人阅读

摘要：思路二指针最大长度现在我们从回数的特点入手。因此，假设当前得到的回数的最大长度为，我们可以判断或者是不是回数。假设此时指针指向，而已知最大回数子字符串的长度为。

题目要求

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"

翻译过来就是说：在一个字符串中寻找最长的子字符串，该字符串是回数（即从左往右和从右往左读的结果是相同的）。该字符串的最大长度为1000

思路一：头指针+尾指针

遍历字符串，找到当前头指针的元素下一次出现时的下标，并且判断该子字符串是否是回数。

    public String longestPalindrome(String s) {
            StringBuilder result = new StringBuilder();
            int resultLength = 0;
            
            StringBuilder temp = new StringBuilder();
            for(int i = 0 ; i=i+resultLength ; j = s.substring(0, j).lastIndexOf(s.charAt(i))){
                    temp = new StringBuilder(s.substring(i, j+1));
                    if(temp.toString().equals(temp.reverse().toString())){
                        result = temp;
                        resultLength = temp.length();
                        break;
                    }    
                }
            }
            return result.toString();
        }

在该方法中，已经对遍历进行了优化，尽可能减少了无效遍历，例如当长度一定小于当前结果的最大长度时，跳出当前循环并进入下一个遍历。但是仍然有很多无效的遍历，因此该答案最后还是超时的。

思路二：指针+最大长度

现在我们从回数的特点入手。
假若一个字符串是一个回数，那么该字符串内部一定还存在更多的回数。例如，abbbcbbba是一个回数，那么bbbcbbb一定是一个回数，那么bcb也是回数，最后到b。同理，bccb是一个回数，那么cc也是一个回数。因此可以看出，假设当前一个字符串是回数，那么加上两侧的字符可能还是回数。假设当前一个字符串不是回数，那么加上右侧的字符可能构成一个回数。
因此，假设当前得到的回数的最大长度为n，我们可以判断n+1或者n+2是不是回数。
为什么这么判断呢？下面给出证明。
我们假设有一个字符串xxxxxxxxabaxxxxxxs，其中x代表任意字符。
假设此时指针指向s，而已知最大回数子字符串的长度为3。我们只需要判断xxxs以及xxxxs是不是回数。无需判断xxs乃至更近是因为它们的长度必然无法超过当前的最大长度。而无需判断xxxxxs乃至更远是因为假如xxxxxs是回数，那么xxxx一定是回数，则当前的最大长度为4而不是3，与题设不符。所以只需判断两种情况。
这里就充分利用了回数的性质，省去了很多无效的遍历

    public String longestPalindrome2(String s) {
        StringBuilder result = new StringBuilder();
        int curLength = 0;
        
        for(int i = 0 ; i
思路三：由中间至两边找回数
思路三就像是思路一的彻底反转。思路一优先寻找回数的边缘，而思路三则直接从中间开始寻找，直至找到最远的边缘。
正如上面所说，回数的中间可能是一个单值，如aba中的b；也可能是双值，如abba中的bb。
我们可以对当前下标上的单值双值都进行尝试
以下是我在leetcode上找到的一个实现（88%）
public class Solution {
private int lo, maxLen;

public String longestPalindrome(String s) {
    int len = s.length();
    if (len < 2)
        return s;
    
    for (int i = 0; i < len-1; i++) {
         extendPalindrome(s, i, i);  //assume odd length, try to extend Palindrome as possible
         extendPalindrome(s, i, i+1); //assume even length.
    }
    return s.substring(lo, lo + maxLen);
}

private void extendPalindrome(String s, int j, int k) {
    while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
        j--;
        k++;
    }
    if (maxLen < k - j - 1) {
        lo = j + 1;
        maxLen = k - j - 1;
    }
}}

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

混合云服务器托管 Palindromic Longest Substring SUBSTRING_INDEX

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

转载请注明本文地址：https://www.ucloud.cn/yun/66939.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

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

摘要：通过使用，我们将无论是奇数还是偶数的回文串，都变成了一个以为中心，为半径两个方向扩展的问题。并且就是回文串的长度。 Given a string s, find the longest palindromic substring in s. 这题的意思是找出最长连续回文串。思路来源于此这里描述了一个叫Manacher’s Algorithm的算法。算法首先将输入字符串S，转换...

noONE 2019-08-21 11:55 评论0 收藏0