成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

5. Longest Palindromic Substring

APICloud / 2828人閱讀

摘要：暴力算法就是找到所有每個都進(jìn)行的檢查。時間復(fù)雜度是個調(diào)用平均時長為這里唯一確定用的是頭尾表示。因為的對稱性，我們可以從中間出發(fā)向兩邊延展，找到最長的分為兩種基本情況。奇數(shù)長度出發(fā)點一致，都為偶數(shù)長度出發(fā)點為相鄰的點，和結(jié)束是

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, 每個都進(jìn)行isPalindrome的檢查。時間復(fù)雜度是O(N^3). N^2個substring, 調(diào)用isPalindrome平均時長為O(N).
這里唯一確定substring用的是頭尾(i,j)表示。因為palindrome的對稱性，我們可以從中間出發(fā)向兩邊延展，找到最長的palindrome.
分為ABA, ABBA兩種基本情況。一共有N個位置唯一標(biāo)記點，調(diào)用一次extenPalindrome時間worst case是O(len)，
最大也就是中點位置的O(n/2). 總的時間復(fù)雜度大致為O(N^2/4)

另外還有一種方法，想法來自于palindrome partition那題。 用一個boolean[i,j]表示(i,j)是否為palindrome, 
比較i-1和j+1. 寫過一個，代碼復(fù)雜，跑起來特別慢，特別是"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++;
        }
        // 結(jié)束是s(j)!=s(k)
        // k-1 - (j+1) +1 = k - j -1
        if(maxLen < k - j - 1){
            lo = j + 1;
            maxLen = k - j - 1;
        }
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/66906.html

相關(guān)文章

  • LeetCode-5 Longest Palindromic Substring

    摘要：題目解析題目是要找出最長的回文字符串，拿到題目的第一反應(yīng)是遍歷子串，然后一直替換最長的子字符串即可了。但是這種解法遇到極端輸入狀況就會超時，指定的最長長度為，遍歷子串需要兩次循環(huán)，判斷回文需要一次循環(huán)，所以總的效率為，那么極端狀況會超時。 題目 Given a string s, find the longest palindromic substring in s. You may ...

    psychola 評論0 收藏0

  • Leetcode 5 Longest Palindromic Substring 最長回文子串

    摘要：難度題目是說給出一個字符串求出這個字符串的最長回文的子串回文是指前后完全對稱的字符串像是之類的都算是回文奇數(shù)字母的回文和偶數(shù)字母的回文中心是不一樣的奇數(shù)字母比如的中心在中間字母上偶數(shù)字母比如的回文在中間兩字母的中心上由此可見回文中心點實際上 Given a string s, find the longest palindromic substring in s. You may as...

    NotFound 評論0 收藏0

  • leetcode 5 Longest Palindromic Substring Java &

    摘要：回文的意思就是反轉(zhuǎn)字符串后和原字符串相等。因為這種想法沒次都是兩邊同時擴展。所以要分目標(biāo)字符串長度為奇數(shù)目標(biāo)字符串為偶數(shù)兩種情況。 題目詳情 Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.題目的意思是輸入...

    JessYanCoding 評論0 收藏0

  • [Leetcode] Longest Palindromic Substring 最長回文子字符串

    摘要：這種解法中，外層循環(huán)遍歷的是子字符串的中心點，內(nèi)層循環(huán)則是從中心擴散，一旦不是回文就不再計算其他以此為中心的較大的字符串。 Longest Palindromic Substring Given a string S, find the longest palindromic substring in S. You may assume that the maximum length ...

    KnewOne 評論0 收藏0

  • LeetCode——Longest Palindromic Substring

    摘要：題目即求最長回文子序列原題鏈接此篇博客僅為學(xué)習(xí)記錄我的解法及代碼暴力解決，用及進(jìn)行兩層遍歷循環(huán)中套一層循環(huán)，用遍歷，求最長回文序列字符串，同時用變量記錄最長子序列這種寫法很暴力，效率很低，一層循環(huán)，一層循環(huán)，回文序列對比一層，時間復(fù)雜度為辣 題目： Given a string s, find the longest palindromic substring in s. You ma...

    shevy 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<