LeetCode解題報告-5.Longest Palindromic Substring

hardタイプの問題に対して、今は本当にHoldではないという意味です。しばらく使わないでください。私はeasuryとmediumを使って後でまた戦います。2016/10/10プログラミング言語はJavaで、コードは私のGitHubに管理されています。テストケースも含まれています。各種の批判を歓迎します。
テーマ——Longest Palindromic Substring
Given a string S，find the longest palindromic substring in S.You may asume that the maximlength of S is 10000，and the exists one unique longest palindromic substring.
答えを出す

タイトルの大意は文字列Sを与え、Sの最長の回文部分列、つまり最長の対称部分列を探し出す。Sが一番長いと仮定しても良いし、一番上の長男串だけが存在します。

解く構想

は、まず、対称的なサブストリングであるならば、長さ値は2つあり得る。奇数と偶数は、この2つの方法でサブストリングを拡張する。

は2つの大域変数を設定し、1つはサブストリングの最低位置を保存し、1つはサブストリングの長さを保存して、必要なサブストリングを返します。

コード実現

public class Solution {
    
    private int maxLen;
    
    private int low;
    
    public String longestPalindrome(String s) {
        if (s.length() < 2) {
            return s;
        }
        for (int i = 0; i < s.length()-1; i++) {
            extendPalindrome(s, i, i);
            extendPalindrome(s, i, i+1);
        }
        return s.substring(low, low + maxLen);
    }
    
    public void extendPalindrome(String s, int i, int j) {
        while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            i--;
            j++;
        }
        if (maxLen < j - i - 1) {
            maxLen = j - i - 1;
            low = i + 1;
        }
    }
}

小結の構想は難しくないですが、この問題を解くには細部と境界条件に注意する必要があります。一つ目は、方法におけるiとjの値の限定である。i>0を取ると、「bb」という文字列についてエラーを解く。二つ目は、maxLenの比較対象であり、j-i-1であり、iとjの値が変わった後は、サイクル条件を満たしていないので、前回の変更値を取ります。