{"id":1052,"date":"2025-12-25T08:40:28","date_gmt":"2025-12-25T00:40:28","guid":{"rendered":"https:\/\/www.guanhaobo.cn\/?p=1052"},"modified":"2025-12-25T08:40:28","modified_gmt":"2025-12-25T00:40:28","slug":"leetcode-1143-%e6%9c%80%e9%95%bf%e5%85%ac%e5%85%b1%e5%ad%90%e5%ba%8f%e5%88%97","status":"publish","type":"post","link":"https:\/\/www.guanhaobo.cn\/?p=1052","title":{"rendered":"LeetCode 1143 \u2013 \u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217"},"content":{"rendered":"<h1>\u9898\u76ee\u63cf\u8ff0<\/h1>\n<p>\u7ed9\u5b9a\u4e24\u4e2a\u5b57\u7b26\u4e32 text1 \u548c text2\uff0c\u8fd4\u56de\u8fd9\u4e24\u4e2a\u5b57\u7b26\u4e32\u7684\u6700\u957f \u516c\u5171\u5b50\u5e8f\u5217 \u7684\u957f\u5ea6\u3002\u5982\u679c\u4e0d\u5b58\u5728 \u516c\u5171\u5b50\u5e8f\u5217 \uff0c\u8fd4\u56de 0 \u3002<br \/>\n\u4e00\u4e2a\u5b57\u7b26\u4e32\u7684 \u5b50\u5e8f\u5217 \u662f\u6307\u8fd9\u6837\u4e00\u4e2a\u65b0\u7684\u5b57\u7b26\u4e32\uff1a\u5b83\u662f\u7531\u539f\u5b57\u7b26\u4e32\u5728\u4e0d\u6539\u53d8\u5b57\u7b26\u7684\u76f8\u5bf9\u987a\u5e8f\u7684\u60c5\u51b5\u4e0b\u5220\u9664\u67d0\u4e9b\u5b57\u7b26\uff08\u4e5f\u53ef\u4ee5\u4e0d\u5220\u9664\u4efb\u4f55\u5b57\u7b26\uff09\u540e\u7ec4\u6210\u7684\u65b0\u5b57\u7b26\u4e32\u3002<br \/>\n\u4f8b\u5982\uff0c&#8221;ace&#8221; \u662f &#8220;abcde&#8221; \u7684\u5b50\u5e8f\u5217\uff0c\u4f46 &#8220;aec&#8221; \u4e0d\u662f &#8220;abcde&#8221; \u7684\u5b50\u5e8f\u5217\u3002<br \/>\n\u4e24\u4e2a\u5b57\u7b26\u4e32\u7684 \u516c\u5171\u5b50\u5e8f\u5217 \u662f\u8fd9\u4e24\u4e2a\u5b57\u7b26\u4e32\u6240\u5171\u540c\u62e5\u6709\u7684\u5b50\u5e8f\u5217\u3002<\/p>\n<p>\u793a\u4f8b\uff1a<br \/>\n\u8f93\u5165\uff1atext1 = &#8220;abcde&#8221;, text2 = &#8220;ace&#8221;<br \/>\n\u8f93\u51fa\uff1a3<br \/>\n\u89e3\u91ca\uff1a\u6700\u957f\u516c\u5171\u5b50\u5e8f\u5217\u662f &#8220;ace&#8221; \uff0c\u5b83\u7684\u957f\u5ea6\u4e3a 3 \u3002<\/p>\n<h1>\u9898\u76ee\u5206\u6790<\/h1>\n<p>\u52a8\u6001\u89c4\u5212<br \/>\n\u8bbe dp[i][j] \u8868\u793a text1 \u7684\u524d i \u4f4d\u4e0e text2 \u7684\u524d j \u4f4d\u6700\u957f\u516c\u5171\u5e8f\u5217\u7684\u957f\u5ea6\uff0c\u5219<br \/>\n&#8211; i \u548c j \u5b57\u7b26\u76f8\u7b49\u65f6\uff0c<code>dp[i][j] = dp[i-1][j-1] + 1<\/code><br \/>\n&#8211; i \u548c j \u5b57\u7b26\u4e0d\u7b49\u65f6\uff0c<code>dp[i][j] = max(dp[i-1][j], dp[i][j-1])<\/code><\/p>\n<p>\u65f6\u95f4\u590d\u6742\u5ea6 O(m * n)\uff0cm \u548c n \u662f\u4e24\u4e2a\u5b57\u7b26\u7684\u957f\u5ea6<\/p>\n<h1>Java<\/h1>\n<pre><code class=\"language-java line-numbers\">public int longestCommonSubsequence(String text1, String text2) {\n    int m = text1.length(), n = text2.length();\n    int[][] dp = new int[m + 1][n + 1];\n    for (int i = 1; i &lt;= m; i++) {\n        for (int j = 1; j &lt;= n; j++) {\n            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {\n                dp[i][j] = dp[i - 1][j - 1] + 1;\n            } else {\n                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);\n            }\n        }\n    }\n    return dp[m][n];\n}\n<\/code><\/pre>\n<h1>Kotlin<\/h1>\n<pre><code class=\"language-kotlin line-numbers\">fun longestCommonSubsequence(text1: String, text2: String): Int {\n    val m = text1.length\n    val n = text2.length\n    val dp = Array(m + 1) { IntArray(n + 1) }\n    for (i in 1..m) {\n        for (j in 1..n) {\n            if (text1[i - 1] == text2[j - 1]) {\n                dp[i][j] = dp[i - 1][j - 1] + 1\n            } else {\n                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])\n            }\n        }\n    }\n    return dp[m][n]\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u63cf\u8ff0 \u7ed9\u5b9a\u4e24\u4e2a\u5b57\u7b26\u4e32 text1 \u548c text2\uff0c\u8fd4\u56de\u8fd9\u4e24\u4e2a\u5b57\u7b26\u4e32\u7684\u6700\u957f \u516c\u5171\u5b50\u5e8f\u5217 \u7684\u957f\u5ea6\u3002\u5982\u679c\u4e0d\u5b58\u5728  [&hellip;]<\/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-1052","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\/1052","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=1052"}],"version-history":[{"count":1,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/1052\/revisions"}],"predecessor-version":[{"id":1053,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/1052\/revisions\/1053"}],"wp:attachment":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1052"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1052"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1052"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}