最長回文サブストリング(Java動的計画)Longest Palindromic Substring

1806 ワード

Longest Palindromic Substring
LeetCode原題は、ここでは主に自分のダイナミックな計画解法と考え方を述べ、これを理解するのに役立つことを望んでいます.
暴力解法はすべての子列を遍歴し,文字列に戻るか否かを逐一判断する.次に暴力解法を最適化し,暴力解法の問題は文字列の特性を用いず,定義を用いて文字列が文字列であるか否かを検証することであるため,この問題の問題点は文字列の特性を利用することにある.文字列が文字列に戻る場合は、左右の文字を除いても返事です.文字列を1つ返し、左右に同じ文字を付けたものであり、文字列を返したものともいえる.インデックスiとjを使用して、インデックスiからjまでの文字列のサブ列を表すと、次のようになります.
dp[i][j]    i j        
dp[i][j] = true     ,    false

dp[i][i]      ,    
         :dp[i][j] = dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
    dp[i][j]       dp[i + 1][j - 1],          
1、       ,  true
2、       ,          true
3、          ,       

1、2次元配列記憶dpの結果値を定義する2、1文字(始点終点インデックスが同じ)すべてtrue 3、2文字同じ文字がtrue(配列が境界を越えないように注意)4、順次3文字、4文字をループ・・・5、始点インデックスi、サブ列長kがあれば終点インデックスj(配列境界問題にも注意)6、比較回文サブ列長と保存されたresult長
class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        boolean[][] dp = new boolean[len][len];//<1>
        String result = s.substring(0, 1);
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;//<2>
        }
        for (int i = 0; i < len - 1; i++) {
            dp[i][i + 1] = s.charAt(i) == s.charAt(i + 1);//<3>
            if (dp[i][i + 1]) {
                result = s.substring(i, i + 1 + 1);
            }
        }        
        //<4>
        for (int k = 3; k <= len; k++) {
            for (int i = 0; (i + k) <= len; i++) {
                int j = i + k - 1;//<5>
                dp[i][j] = dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
                if (dp[i][j] && (j - i + 1) > result.length()) {//<6>
                    result = s.substring(i, j + 1);
                }
            }
        }
        return result;
    }
}