{"id":797,"date":"2022-07-20T03:21:43","date_gmt":"2022-07-20T03:21:43","guid":{"rendered":"https:\/\/blog.liuyingjie.com.cn\/?p=797"},"modified":"2023-08-13T08:12:23","modified_gmt":"2023-08-13T08:12:23","slug":"14-longest-common-prefix","status":"publish","type":"post","link":"https:\/\/blog.liuyingjie.com.cn\/?p=797","title":{"rendered":"14. \u6700\u957f\u516c\u5171\u524d\u7f00"},"content":{"rendered":"\n<p>\u65b9\u6cd5\u4e00\uff1a<\/p>\n\n\n\n<p>\u6a2a\u5411\u626b\u63cf<br>\u7528LCP(S1&#8230;Sn)\u8868\u793a\u5b57\u7b26\u4e32S1&#8230;Sn\u7684\u6700\u957f\u516c\u5171\u524d\u7f00\u3002<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"xml\" class=\"language-xml\">LCP(S_1......S_n) = LCP(LCP(LCP(S_1,S_2),S_3),...S_n)<\/code><\/pre>\n\n\n\n<p>\u4f9d\u6b21\u904d\u5386\u5b57\u7b26\u4e32\u6570\u7ec4\u4e2d\u7684\u6bcf\u4e2a\u5b57\u7b26\u4e32\uff0c\u5982\u679c\u5c1a\u672a\u904d\u5386\u5b8c\u6240\u4ee5\u7684\u5b57\u7b26\u4e32\u65f6\uff0c\u6700\u957f\u516c\u5171\u524d\u7f00\u5df2\u7ecf\u662f\u7a7a\u5b57\u7b26\u4e32\uff0c\u5219\u6700\u957f\u516c\u5171\u524d\u7f00\u4e00\u5b9a\u662f\u7a7a\u5b57\u7b26\u4e32\u3002\u76f4\u63a5\u8fd4\u56de\u7a7a\u5b57\u7b26\u4e32\u3002<\/p>\n\n\n\n<p>Python3 \u4ee3\u7801\u89e3\u6cd5<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"python\" class=\"language-python\">class Solution:\n    def longestCommonPrefix(self, strs: List[str]) -&gt; str:\n        if not strs:\n            return \"\"\n\n        prefix, cont = strs[0], len(strs)\n        for i in range(1, cont):\n            prefix = self.lcp(prefix, strs[i])\n            if not prefix:\n                break\n\n        return prefix\n\n    def lcp(self, str1, str2):\n        length, index = min(len(str1), len(str2)), 0\n        while index &lt; length and str1[index] == str2[index]:\n            index += 1\n        return str1[:index]<\/code><\/pre>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/blog.liuyingjie.com.cn\/wp-content\/uploads\/2022\/07\/14.-\u6700\u957f\u516c\u5171\u524d\u7f00.png\" alt=\"\"\/><\/figure>\n\n\n\n<p><strong>Source: LeetCode\uff08The title reproduced in this blog is for personal study use only\uff09<\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u65b9\u6cd5\u4e00\uff1a \u6a2a\u5411\u626b\u63cf\u7528LCP(S1&#8230;Sn)\u8868\u793a\u5b57\u7b26\u4e32S1&#8230;Sn\u7684\u6700\u957f\u516c\u5171\u524d\u7f00\u3002 \u4f9d\u6b21\u904d\u5386 &hellip; <a href=\"https:\/\/blog.liuyingjie.com.cn\/?p=797\" class=\"more-link\">\u7ee7\u7eed\u9605\u8bfb<span class=\"screen-reader-text\">14. \u6700\u957f\u516c\u5171\u524d\u7f00<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"inline_featured_image":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-797","post","type-post","status-publish","format-standard","hentry","category-leetcode"],"_links":{"self":[{"href":"https:\/\/blog.liuyingjie.com.cn\/index.php?rest_route=\/wp\/v2\/posts\/797","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.liuyingjie.com.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.liuyingjie.com.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.liuyingjie.com.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.liuyingjie.com.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=797"}],"version-history":[{"count":9,"href":"https:\/\/blog.liuyingjie.com.cn\/index.php?rest_route=\/wp\/v2\/posts\/797\/revisions"}],"predecessor-version":[{"id":990,"href":"https:\/\/blog.liuyingjie.com.cn\/index.php?rest_route=\/wp\/v2\/posts\/797\/revisions\/990"}],"wp:attachment":[{"href":"https:\/\/blog.liuyingjie.com.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=797"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.liuyingjie.com.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=797"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.liuyingjie.com.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=797"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}