{"id":1049,"date":"2025-12-25T07:50:59","date_gmt":"2025-12-24T23:50:59","guid":{"rendered":"https:\/\/www.guanhaobo.cn\/?p=1049"},"modified":"2025-12-25T07:50:59","modified_gmt":"2025-12-24T23:50:59","slug":"leetcode-5-%e6%9c%80%e9%95%bf%e5%9b%9e%e6%96%87%e5%ad%90%e4%b8%b2","status":"publish","type":"post","link":"https:\/\/www.guanhaobo.cn\/?p=1049","title":{"rendered":"LeetCode 5 \u2013 \u6700\u957f\u56de\u6587\u5b50\u4e32"},"content":{"rendered":"

\u9898\u76ee\u63cf\u8ff0<\/h1>\n

\u7ed9\u4f60\u4e00\u4e2a\u5b57\u7b26\u4e32 s\uff0c\u627e\u5230 s \u4e2d\u6700\u957f\u7684 \u56de\u6587 \u5b50\u4e32\u3002<\/p>\n

\u793a\u4f8b\uff1a
\n\u8f93\u5165\uff1as = “babad”
\n\u8f93\u51fa\uff1a”bab”
\n\u89e3\u91ca\uff1a”aba” \u540c\u6837\u662f\u7b26\u5408\u9898\u610f\u7684\u7b54\u6848\u3002<\/p>\n

\u9898\u76ee\u5206\u6790<\/h1>\n

\u52a8\u6001\u89c4\u5212
\n\u8bbe dp[i][j] \u8868\u793a\u5728\u5b50\u4e32 [i, j] \u662f\u5426\u56de\u6587\uff0c\u5728 s[i] = s[j] \u65f6
\n– j – i <= 1, dp[i][j] = true
\n– j – i > 1\uff0cdp[i][j] = dp[i + 1][j – 1]<\/p>\n

\u7531\u4e8e\u8f6c\u79fb\u65b9\u7a0b\u4e2d\u662f i+1\uff0c\u6240\u4ee5 i \u9700\u8981\u5012\u5e8f\u904d\u5386\uff0cj \u7684\u987a\u5e8f\u5219\u65e0\u6240\u8c13<\/p>\n

\u65f6\u95f4\u590d\u6742\u5ea6 O(n * n)\uff0cn \u4e3a s \u7684\u957f\u5ea6\u3002<\/p>\n

Java<\/h1>\n
public String longestPalindrome(String s) {\n    int len = s.length();\n    boolean[][] dp = new boolean[len][len];\n    int left = 0, right = 0;\n    for (int i = len - 1; i >= 0; i--) {\n        for (int j = i; j < len; j++) {\n            if (s.charAt(i) == s.charAt(j)) {\n                if (j - i <= 1) {\n                    dp[i][j] = true;\n                } else if (i + 1 < len && j - 1 >= 0) {\n                    dp[i][j] = dp[i + 1][j - 1];\n                }\n                if (dp[i][j] && j - i > right - left) {\n                    left = i;\n                    right = j;\n                }\n            }\n        }\n    }\n    return s.substring(left, right + 1);\n}\n<\/code><\/pre>\n
Kotlin<\/h1>\n
fun longestPalindrome(s: String): String {\n    val dp = Array(s.length) { BooleanArray(s.length) }\n    var start = 0\n    var end = 0\n    for (i in s.indices.reversed()) {\n        for (j in i until s.length) {\n            if (s[i] == s[j]) {\n                if (j - i <= 1) {\n                    dp[i][j] = true\n                } else if (i + 1 in s.indices && j - 1 in s.indices) {\n                    dp[i][j] = dp[i + 1][j - 1]\n                }\n            }\n            if (dp[i][j] && j - i > end - start) {\n                start = i\n                end = j\n            }\n        }\n    }\n    return s.substring(start, end + 1)\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9898\u76ee\u63cf\u8ff0 \u7ed9\u4f60\u4e00\u4e2a\u5b57\u7b26\u4e32 s\uff0c\u627e\u5230 s \u4e2d\u6700\u957f\u7684 \u56de\u6587 \u5b50\u4e32\u3002 \u793a\u4f8b\uff1a \u8f93\u5165\uff1as = “babad […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[20,40,45],"class_list":["post-1049","post","type-post","status-publish","format-standard","hentry","category-algo","tag-leetcode","tag-40","tag-45"],"_links":{"self":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/1049","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1049"}],"version-history":[{"count":1,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/1049\/revisions"}],"predecessor-version":[{"id":1051,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/1049\/revisions\/1051"}],"wp:attachment":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1049"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1049"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1049"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}