leetcode5 Longest Palindromic Substring 最長且為回數的子字符

Imfan 發布于2019-08-14 18:01 / 352人閱讀

摘要：思路二指針最大長度現在我們從回數的特點入手。因此，假設當前得到的回數的最大長度為，我們可以判斷或者是不是回數。假設此時指針指向，而已知最大回數子字符串的長度為。

題目要求

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;
    }
}}

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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