{"id":1965,"date":"2022-05-11T14:55:00","date_gmt":"2022-05-11T14:55:00","guid":{"rendered":"https:\/\/www.zttofficial.com\/?p=1965"},"modified":"2022-05-11T14:58:23","modified_gmt":"2022-05-11T14:58:23","slug":"%e5%81%9a%e9%a1%8c%e7%ad%86%e8%a8%98%ef%bc%9alongest-common-prefix-java","status":"publish","type":"post","link":"https:\/\/www.zttofficial.com\/?p=1965","title":{"rendered":"\u505a\u984c\u7b46\u8a18\uff1aLongest Common Prefix (Java)"},"content":{"rendered":"\n

\u9084\u6eff\u96e3\u7684\u4e00\u9053\u984c\u3002<\/p>\n\n\n\n

\u984c\u76ee\u63cf\u8ff0\uff1a<\/strong><\/p>\n\n\n\n

\u7de8\u5beb\u4e00\u500b\u51fd\u6578\u4f86\u67e5\u627e\u5b57\u7b26\u4e32\u6578\u7d44\u4e2d\u6700\u9577\u7684\u5171\u6709\u524d\u7db4\u5b57\u7b26\u4e32\u3002<\/p>\n\n\n\n

\u5982\u679c\u6c92\u6709\u5171\u6709\u524d\u7db4\uff0c\u5247\u8fd4\u56de\u4e00\u500b\u7a7a\u5b57\u7b26\u4e32\"\"<\/kbd>\u3002<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input: strs = [\"flower\",\"flow\",\"flight\"]\nOutput: \"fl\"<\/code><\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input: strs = [\"dog\",\"racecar\",\"car\"]\nOutput: \"\"\nExplanation: There is no common prefix among the input strings.<\/code><\/pre>\n\n\n\n
Horizontal scanning: <\/strong><\/p>\n\n\n\n
\u81ea\u5df1\u5617\u8a66\u7684\u65b9\u6cd5\uff1a<\/p>\n\n\n\n
class Solution {\n    public String longestCommonPrefix(String[] strs)\n    {\n        int size = strs.length;\n        if (size == 0)\n            return \"\";\n\n        if (size == 1)\n            return strs[0];\n\n        Arrays.sort(strs);\n        int end = Math.min(strs[0].length(), strs[size-1].length());\n        int i = 0;\n        while (i < end && strs[0].charAt(i) == strs[size-1].charAt(i) )\n            i++;\n        String pre = strs[0].substring(0, i);\n        return pre;\n    }\n}<\/code><\/pre>\n\n\n\n
1 ms<\/p>\n\n\n\n
Vertical scanning:<\/strong><\/p>\n\n\n\n
Solution \u4e2d\u63d0\u4f9b\u7684\u65b9\u6cd5\u4e8c\uff1a<\/p>\n\n\n\n
public String longestCommonPrefix(String[] strs) {\n    if (strs == null || strs.length == 0) return \"\";\n    for (int i = 0; i < strs[0].length() ; i++){\n        char c = strs[0].charAt(i);\n        for (int j = 1; j < strs.length; j ++) {\n            if (i == strs[j].length() || strs[j].charAt(i) != c)\n                return strs[0].substring(0, i);             \n        }\n    }\n    return strs[0];\n}<\/code><\/pre>\n\n\n\n
Divide and conquer:<\/strong><\/p>\n\n\n\n
Solution \u4e2d\u63d0\u4f9b\u7684\u65b9\u6cd5\u4e09\uff1a<\/p>\n\n\n\n
public String longestCommonPrefix(String[] strs) {\n    if (strs == null || strs.length == 0) return \"\";    \n        return longestCommonPrefix(strs, 0 , strs.length - 1);\n}\n\nprivate String longestCommonPrefix(String[] strs, int l, int r) {\n    if (l == r) {\n        return strs[l];\n    }\n    else {\n        int mid = (l + r)\/2;\n        String lcpLeft =   longestCommonPrefix(strs, l , mid);\n        String lcpRight =  longestCommonPrefix(strs, mid + 1,r);\n        return commonPrefix(lcpLeft, lcpRight);\n   }\n}\n\nString commonPrefix(String left,String right) {\n    int min = Math.min(left.length(), right.length());       \n    for (int i = 0; i < min; i++) {\n        if ( left.charAt(i) != right.charAt(i) )\n            return left.substring(0, i);\n    }\n    return left.substring(0, min);\n}<\/code><\/pre>\n\n\n\n
Binary search<\/strong>:<\/p>\n\n\n\n
Solution \u4e2d\u63d0\u4f9b\u7684\u65b9\u6cd5\u56db\uff1a<\/p>\n\n\n\n
public String longestCommonPrefix(String[] strs) {\n    if (strs == null || strs.length == 0)\n        return \"\";\n    int minLen = Integer.MAX_VALUE;\n    for (String str : strs)\n        minLen = Math.min(minLen, str.length());\n    int low = 1;\n    int high = minLen;\n    while (low <= high) {\n        int middle = (low + high) \/ 2;\n        if (isCommonPrefix(strs, middle))\n            low = middle + 1;\n        else\n            high = middle - 1;\n    }\n    return strs[0].substring(0, (low + high) \/ 2);\n}\n\nprivate boolean isCommonPrefix(String[] strs, int len){\n    String str1 = strs[0].substring(0,len);\n    for (int i = 1; i < strs.length; i++)\n        if (!strs[i].startsWith(str1))\n            return false;\n    return true;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9084\u6eff\u96e3\u7684\u4e00\u9053\u984c\u3002 \u984c\u76ee\u63cf\u8ff0\uff1a \u7de8\u5beb\u4e00\u500b\u51fd\u6578\u4f86\u67e5\u627e\u5b57\u7b26\u4e32\u6578\u7d44\u4e2d\u6700\u9577\u7684\u5171\u6709\u524d\u7db4\u5b57\u7b26\u4e32\u3002 \u5982\u679c\u6c92\u6709\u5171\u6709\u524d\u7db4\uff0c\u5247\u8fd4\u56de\u4e00\u500b\u7a7a\u5b57\u7b26\u4e32””\u3002 Example 1: Example 2: Horizontal scanning: \u81ea\u5df1\u5617\u8a66\u7684\u65b9\u6cd5\uff1a 1 ms Vertical scanning: Solution \u4e2d\u63d0\u4f9b\u7684\u65b9\u6cd5\u4e8c\uff1a Divide and conquer: Solution \u4e2d\u63d0\u4f9b\u7684\u65b9\u6cd5\u4e09\uff1a Binary search: Solution \u4e2d\u63d0\u4f9b\u7684\u65b9\u6cd5\u56db\uff1a<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[135,2],"tags":[137],"class_list":["post-1965","post","type-post","status-publish","format-standard","hentry","category-135","category-all","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/www.zttofficial.com\/index.php?rest_route=\/wp\/v2\/posts\/1965","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.zttofficial.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.zttofficial.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.zttofficial.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.zttofficial.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1965"}],"version-history":[{"count":2,"href":"https:\/\/www.zttofficial.com\/index.php?rest_route=\/wp\/v2\/posts\/1965\/revisions"}],"predecessor-version":[{"id":1967,"href":"https:\/\/www.zttofficial.com\/index.php?rest_route=\/wp\/v2\/posts\/1965\/revisions\/1967"}],"wp:attachment":[{"href":"https:\/\/www.zttofficial.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1965"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.zttofficial.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1965"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.zttofficial.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1965"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}