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

資訊專欄INFORMATION COLUMN

Leetcode 5 Longest Palindromic Substring 最長回文子串

NotFound / 892人閱讀

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

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"

難度:Medium

題目是說, 給出一個字符串, 求出這個字符串的最長"回文"的子串. 回文是指前后完全對稱的字符串, 像是abba cabac 之類的都算是回文.

奇數(shù)字母的回文和偶數(shù)字母的回文中心是不一樣的, 奇數(shù)字母比如aba的中心在中間字母上, 偶數(shù)字母比如abba的回文在中間兩字母的中心上, 由此可見, 回文中心點實際上最小間隔是"半個"字符. 我們可以考慮回文中心以半個字符間距不斷移動, 去尋找最長回文子串.

public class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        int maxl = 0;
        int maxr = 0;
        int maxLen = 1;
        for (int k = 0; k < len * 2 - 1; k++) {
            int base = 0;
            int plen = 1;
            int left = k / 2;
            int right = k / 2;
            if (k % 2 == 1) {
                base = 1;
                plen = 0;
                left = (k - 1) / 2;
                right = (k + 1) / 2;
            }
            for (int i = base; k - i >= 0 && (k + i) / 2 <= len - 1; i = i + 2) {
                int l = (k - i) / 2;
                int r = (k + i) / 2;
                if (s.charAt(l) != s.charAt(r)) {
                    break;
                }
                left = l;
                right = r;
                plen = r - l + 1;
            }
            if (plen > maxLen) {
                maxl = left;
                maxr = right;
                maxLen = plen;
            }
        }
        return s.substring(maxl, maxr + 1);
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.longestPalindrome("a"));
        System.out.println(s.longestPalindrome("aba"));
        System.out.println(s.longestPalindrome("aa"));
        System.out.println(s.longestPalindrome("abac"));
        System.out.println(s.longestPalindrome("baab"));
    }
}

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

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

相關(guān)文章

  • LeetCode.5 最長回文子串(longest-palindromic-substring)(J

    摘要：一題目最長回文子串給定一個字符串，找到中最長的回文子串。你可以假設(shè)的最大長度為。示例輸入輸出注意也是一個有效答案。 一、題目 最長回文子串： 給定一個字符串 s，找到 s 中最長的回文子串。你可以假設(shè) s 的最大長度為 1000。 示例 1： 輸入: babad輸出: bab注意: aba 也是一個有效答案。 示例 2： 輸入: cbbd輸出: bb 二、我的答案 思路 1.排...

    Steven 評論0 收藏0

  • LeetCode——Longest Palindromic Substring

    摘要：題目即求最長回文子序列原題鏈接此篇博客僅為學(xué)習(xí)記錄我的解法及代碼暴力解決，用及進行兩層遍歷循環(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

  • 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（動態(tài)規(guī)

    摘要：題目描述給定一個字符串，找到中最長的回文子串。你可以假設(shè)的最大長度為。示例輸入輸出注意也是一個有效答案。示例輸入輸出思路分析暴力解法解決一個問題如果沒有思路，就要想辦法從簡單粗暴的解法開始，然后想辦法優(yōu)化它。 題目描述 https://leetcode-cn.com/probl... 給定一個字符串 s，找到 s 中最長的回文子串。你可以假設(shè)?s 的最大長度為 1000。 示例 1： ...

    neuSnail 評論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

發(fā)表評論

0條評論

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