DP 回文 - wenzhoullq/leetcode GitHub Wiki
存在性
模板
比较经典的模板,值得注意的是从i=len到i=1之间的遍历
boolean[][] dp=new boolean[len+1][len+1];
for(int i=len;i>=1;i--){
for(int j=i;j<=len;j++){
if(j==i||j-i>=2&&dp[i+1][j-1]&&s.charAt(i-1)==s.charAt(j-1)||j-i==1&&s.charAt(i-1)==s.charAt(j-1)) dp[i][j]=true;
}
}
题目
中心扩散
int left = len/2-1,right = len - left -1;
while(left>=0&&s1.charAt(left)==s2.charAt(right)){
left++;
right--;
}
return left == -1;
题目
1616. 分割两个字符串得到回文串 先找中间扩散最大的,再找剩余的部分能否满足回文