【LeetCode題解-005】longest Palindrome Substring

テーマ
Given a string s、find the longest palindromic substring in s.You may asume that the maximlength of s 1000.
Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

元の住所:https://leetcode.com/problems/longest-palindromic-substring/
翻訳
文字列sを指定します.sの中で一番長い回文部分列が見つかりました.sの最大長さは1000と仮定できます.
法を解く
解法一:一番長い公共串
私たちは自然に次のような解決法を思いつきます.
SSを反転させてS’S’にします.SSとS’S’の間の一番長い共通の部分列を見つけました.これも一番長い回文部分列に違いないです.
しかし、このようなやり方には問題があります.

Example 1:
s = 'caba', s1 = 'abac'
s s1           ：'aba'
    
Example 2:
s = 'abacdfgdcaba', s1 = 'abacdgfdcaba'
s s1           ：'abacd'
               

SSの他の部分に非エコーサブストリングの逆複製があると、最長の共通サブストリング法が失敗することが分かる.これを訂正するためには、最も長い共通のサブストリングの候補を見つけるたびに、サブストリングのインデックスが逆のサブストリングの元のインデックスと同じかどうかを確認する必要がある.もし同じなら、今まで見つけた最長の回文子列を更新してみましょう.もしそうでないなら、私たちはこの候補を飛ばして次の候補を探し続けます.
これは、O(n^2)の空間を占有する動的計画解を提供します.(O(n)を使用する空間に改善できます.)
住所にありますhttps://en.wikipedia.org/wiki/Longest_commonsubstring_problemは一番長い公共串に関する内容をもっと読みます.
ここではもう詳しく説明しません.
解法二:暴力法
すべてのサブ文字列の可能な開始位置と終了位置を選択し、返信されていないかを確認します.

文字列の中で文字の出現回数が偶数の場合、必ず最長の文字列

を追加することができる.

文字列中の文字の出現回数が奇数の場合、状況を分けて議論する.

出現回数が1より大きい奇数nであれば、n-1の対応文字を最長の回文部分列に追加することができ、

最終的には最長の回文子列があり、真ん中には単一の文字

も追加できます.

上の2つの組み合わせは、最大の奇数の数の文字を直接に最長の回文部分列

に加えることができる.

すなわちif(奇数の数が現れる文字数==0)、returns.length()

if(奇数の数が出る文字数!=0)、returns.length()-奇数の数が出る文字数+1

解法三:ダイナミック企画
暴力法を改善するためには、レビューを検証する際の不必要な反復計算を避ける方法をまず観察します.abbaa’という例を考慮します.「bab」が回文であることを知っていたら、「abbaa」は必ず回文です.左の頭文字と右の尾文字は同じですから.
P(i,j)P(i,j)の定義を与える.
これは直感的な動的企画解法を生みました.まずアルファベットと二文字の回文を初期化して、三文字の回文を全部見つけて、このように類推します.

/**
     *       
     *
     * @param s
     * @return
     */
public static String longestPalindrome(String s) {
    if (s == null || s.length() < 2) {
        return s;
    }

    int maxLength = 0;
    String longest = null;

    int length = s.length();
    boolean[][] table = new boolean[length][length];

    //         
    for (int i = 0; i < length; i++) {
        table[i][i] = true;
        longest = s.substring(i, i + 1);
        maxLength = 1;
    }

    //            
    for (int i = 0; i < length - 1; i++) {
        if (s.charAt(i) == s.charAt(i + 1)) {
            table[i][i + 1] = true;
            longest = s.substring(i, i + 2);
            maxLength = 2;
        }
    }

    //      2         
    for (int len = 3; len <= length; len++) {
        for (int i = 0, j; (j = i + len - 1) <= length - 1; i++) {
            if (s.charAt(i) == s.charAt(j)) {
                table[i][j] = table[i + 1][j - 1];
                if (table[i][j] && maxLength < len) {
                    longest = s.substring(i, j + 1);
                    maxLength = len;
                }
            } else {
                table[i][j] = false;
            }
        }
    }
    return longest;
}

解法四:中心拡張アルゴリズム
実際には、一定の空間を使うだけで、O(n^2)の時間内にこの問題を解決することができます.これも公式サイトの一種の経典解法です.
回文中心の両側は互いに鏡像であることを観測した.したがって,回文はその中心から展開でき,2 n−1のような中心しかない.
なぜ2 n-12 n−1個で、nn個の中心ではないですか?なぜなら、アルファベット数が偶数の回文の中心は2文字の間にあることができるからです.例えば、「abba」の中心は2つの「b」の間にあります.

/**
     *       
     *            。  ，           ，     2n - 12n−1       。
     *      ：               O(n)O(n)    O(n^2)
     *      ：O(1)
     * @param s
     * @return
     */
public static String longestPalindrome2(String s) {
    if (s == null || s.length() < 1) {
        return "";
    }
    int start = 0, end = 0;
    //            
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}
private static int expandAroundCenter(String s, int left, int right) {
    int L = left, R = right;
    while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
        L--;
        R++;
    }
    return R - L - 1;
}

解法5:Manacherアルゴリズム
これはLeetCode公式サイトの複雑さの一つです.O(n)までの解法です.無意味な爆発です.拝み中です.
興味があれば、住所はここです.https://articles.leetcode.com/longest-palindromic-substring-part-ii/
私は最近仕事が忙しいので、ブラシの数は少し下がるかもしれませんが、週最低3-4の問題を保証します.
Githubアドレス:https://github.com/Bylant/LeetCode
CSDNアドレス:https://blog.csdn.net/ZBylant ウィーチャット公衆番号