リートコード5.最長の回文部分文字列 注釈

ミディアム

推論

• DP
• 横軸は部分文字列の終わりのインデックス、縦軸は始まりのインデックスで、配列の各ポイントは部分文字列の値が等しいかどうかを示します。
• i++、j--のステップでi、jが与えられたとき、すべての条件で回文文字列であることが真

dp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i+1][j-1]

• この2次元配列を2レベルのforループでどのように掃引するのでしょうか？
• 各ポイントはその左下のポイントに依存するため、まずその左下の方向の値を知ることが重要です。
• だから2つの方法があります：
• 1

for(int j = 0; j < s.length(); j++)
	for(int i = 0; i <= j; i++)

• 2

for(int i = s.length() - 1; i >= 0; i--)
	for(int j = s.length() - 1; j >= i; j--)

• 部分文字列について .
• reference www.youtube.com/watch?v=Znz
• substring(a,b)は、添え字が a から b の終わりまでで、a の文字を含み b の文字を含まない文字を取り込むことを意味します。

コーディング

class Solution {
 public String longestPalindrome(String s) {
 if(s.length() <= 1 || s == null) return s;
 
 String res = "";
 int len = s.length();
 boolean[][] dp = new boolean[len][len];
 
 for(int j = 0; j < len; j++){
 for(int i = 0; i <= j; i++){
 dp[i][j] = (s.charAt(i) == s.charAt(j)) && ((j - i) <= 2 || dp[i + 1][j - 1]);
 if(dp[i][j] && (j - i + 1) > res.length())
 res = s.substring(i, j + 1);
 }
 }
 
 return res;
 }
}

• reference www.youtube.com/watch?v=Znz
• ダイナミックプログラミング
• 08/04/20