3503.子字符串连接后的最长回文串I

brute force, https://leetcode.cn/problems/longest-palindrome-after-substring-concatenation-i/

给你两个字符串 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 <= 30
s 和 t 仅由小写英文字母组成。

python

from typing import List

class Solution:
    def longestPalindrome(self, s: str, t: str) -> int:
        # 检查字符串是否为回文
        def is_palindrome(sub: str) -> bool:
            return sub == sub[::-1]

        n1, n2 = len(s), len(t)
        max_len = 0

        # 枚举 s 和 t 的所有子串组合
        for i in range(n1 + 1):  # s 的子串起点
            for j in range(i, n1 + 1):  # s 的子串终点
                for k in range(n2 + 1):  # t 的子串起点
                    for l in range(k, n2 + 1):  # t 的子串终点
                        combined = s[i:j] + t[k:l]
                        if is_palindrome(combined):
                            max_len = max(max_len, len(combined))

        return max_len

if __name__ == '__main__':
    s = Solution()
    print(s.longestPalindrome("a", "a"))       # 输出：2
    print(s.longestPalindrome("abc", "def"))   # 输出：1
    print(s.longestPalindrome("b", "aaaa"))    # 输出：4
    print(s.longestPalindrome("abcde", "ecdba"))  # 输出：5
    print(s.longestPalindrome("n", "no"))      # 输出：2

3503.子字符串连接后的最长回文串I ​

3503.子字符串连接后的最长回文串I