给你两个字符串 s
和 t
。
你可以从 s
中选择一个子串(可以为空)以及从 t
中选择一个子串(可以为空),然后将它们 按顺序 连接,得到一个新的字符串。
返回可以由上述方法构造出的 最长 回文串的长度。
回文串 是指正着读和反着读都相同的字符串。
子字符串 是指字符串中的一个连续字符序列。
示例 1:
输入: s = "a", t = "a"
输出: 2
解释:
从 s
中选择 "a"
,从 t
中选择 "a"
,拼接得到 "aa"
,这是一个长度为 2 的回文串。
示例 2:
输入: s = "abc", t = "def"
输出: 1
解释:
由于两个字符串的所有字符都不同,最长的回文串只能是任意一个单独的字符,因此答案是 1。
示例 3:
输入: s = "b", t = "aaaa"
输出: 4
解释:
可以选择 "aaaa"
作为回文串,其长度为 4。
示例 4:
输入: s = "abcde", t = "ecdba"
输出: 5
解释:
从 s
中选择 "abc"
,从 t
中选择 "ba"
,拼接得到 "abcba"
,这是一个长度为 5 的回文串。
提示:
1 <= s.length, t.length <= 1000
s
和 t
仅由小写英文字母组成。dp[i][j]
be the length of the longest answer if we try starting it with s[i]
and ending it with t[j]
.s
, preprocess the length of the longest palindrome starting at index i
as p[i]
.t
, preprocess the length of the longest palindrome ending at index j
as q[j]
.s[i] != t[j]
, then dp[i][j] = max(p[i], q[j])
.dp[i][j] = max(p[i], q[j], 2 + dp[i + 1][j - 1])
.