[LintCode/LeetCode] Longest Palindrome Substring

AaronYuan 發(fā)布于2019-08-14 15:15 / 2591人閱讀

摘要：是左閉右開區(qū)間，所以要。，要理解是和之間只有一個元素。循環(huán)每次的時候，都要更新子串更大的情況。補一種中點延展的方法循環(huán)字符串的每個字符，以該字符為中心，若兩邊為回文，則向兩邊繼續(xù)延展。循環(huán)返回長度最長的回文串即可。

Problem

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Example

Given the string = "abcdzdcab", return "cdzdc".

Challenge

O(n2) time is acceptable. Can you do it in O(n) time.

Note

動規(guī)好題。
.substring(start, end)是左閉右開區(qū)間，所以end要+1。
if (s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j+1][i-1]))，要理解i - j <= 2是i和j之間只有一個元素。
循環(huán)每次i - j > end - start的時候，都要更新子串更大的情況。Time和space都是O(n^2)。

補一種中點延展的方法：循環(huán)字符串的每個字符，以該字符為中心，若兩邊為回文，則向兩邊繼續(xù)延展。如此，每個字符必對應一個最長回文串。循環(huán)返回長度最長的回文串即可。

Solution DP

public class Solution {
    public String longestPalindrome(String s) {
        // Write your code here
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        int start = 0, end = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j <= i; j++) {
                if (s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j+1][i-1])) {
                    dp[j][i] = true;
                    if (end - start < i - j ) {
                        start = j;
                        end = i;
                    }
                }
            }
        }
        return s.substring(start, end+1);
    }
}

方法二：中點延展

public class Solution {
    String longest = "";
    public String longestPalindrome(String s) {
        for (int i = 0; i < s.length(); i++) {
            helper(s, i, 0);
            helper(s, i, 1);
        }
        return longest;
    }
    public void helper(String s, int i, int os) {
        int left = i, right = i + os;
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        String cur = s.substring(left+1, right);
        if (cur.length() > longest.length()) {
            longest = cur;
        }
    }
}

2018-02-03 Added some comments, same thoughts as solution 2

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) return s;
        //return as result
        String longest = s.substring(0, 1);
        for (int i = 0; i < s.length()-1; i++) {
            //get "ABA" type palindrome
            String cur = getPalindrome(s, i, i);
            //get "ABBA" type palindrome, and compare its length with "ABA" type
            if (s.charAt(i+1)==s.charAt(i)) {
                String temp = getPalindrome(s, i, i+1);
                cur = cur.length() > temp.length() ? cur : temp;
            }
            //update longest with cur
            longest = longest.length() > cur.length() ? longest : cur;
        }
        return longest;
    }
    public String getPalindrome(String s, int left, int right) {
        while (left > 0 && right < s.length()-1 && s.charAt(left-1) == s.charAt(right+1)) {
            left--;
            right++;
        }
        //careful with the right bound
        return s.substring(left, right+1);
    }
}

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

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

轉載請注明本文地址：http://systransis.cn/yun/65518.html

5. Longest Palindromic Substring

摘要：暴力算法就是找到所有每個都進行的檢查。時間復雜度是個調用平均時長為這里唯一確定用的是頭尾表示。因為的對稱性，我們可以從中間出發(fā)向兩邊延展，找到最長的分為兩種基本情況。奇數(shù)長度出發(fā)點一致，都為偶數(shù)長度出發(fā)點為相鄰的點，和結束是 Given a string s, find the longest palindromic substring in s. You may assume tha...

APICloud 2019-08-14 17:57 評論0 收藏0
[LintCode/LeetCode] Longest Consecutive Sequence

摘要：先排序，然后用數(shù)組記錄每一位上連續(xù)序列的長度，每次循環(huán)更新最大值存為。 Problem Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Clarification Your algorithm should run in O(n) com...

buildupchao 2019-08-14 16:25 評論0 收藏0
查找字符串最長回文

摘要：查找字符串最長回文思路回文有奇回文和偶回文，是奇回文，是偶回文回文都是中心對稱，找到對稱點后，同時向前后尋找回文的最長串即可奇回文和偶回文可以歸為同一種情況，即以為對稱點，以為對稱點，但為了代碼可讀性，可以分開討論代碼奇回文偶回文本題查找字符串最長回文 Longest Palindromic Substring Given a string s, find the longest ...

CastlePeaK 2019-07-25 12:03 評論0 收藏0
leetcode部分題目答案之JavaScript版

摘要：自己沒事刷的一些的題目，若有更好的解法，希望能夠一起探討項目地址自己沒事刷的一些LeetCode的題目，若有更好的解法，希望能夠一起探討 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...

alphahans 2019-08-21 16:20 評論0 收藏0
[LintCode/LeetCode] Restore IP Addresses

摘要：第一個分割點第二個分割點第三個分割點 Problem Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example Given 25525511135, return [ 255.255.11.135, 255....

bingo 2019-08-14 15:14 評論0 收藏0