Write a function to find the longest common prefix string amongst an array of strings.

算法分析: 题意很简单, 求字符串数组里面的公用前缀. 首先想到的公用前缀指针为i, 1, 2比较, 取最小i, 再1, 3 比较缩小i的范围. 再1和4, 1和5. 这种方法就比较简单, 时间复杂度为: O(n).
但是我采用的是另外一种分治, 递归的方式, 1, 2, 3, 4, 5 五个字符串, 1,2比较得一个, 2,3比较得一个, 4,5比较得一个, 将得到的3个再以此类方法比较下去,使得最后只剩下两个, 然后求得最终结果, 时间复杂度为: O(nlog2n)

Java:

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        int len = strs.length;
        int i = 0;
        if (len == 0)
            return "";
        if (len == 1)
            return strs[0];
        if (len == 2) {
            if (strs[0].equals(strs[1]))
                return strs[0];
            int lena = strs[0].length();
            int lenb = strs[1].length();
            String rst = "";
            for (i = 0; i < lena; i++) {
                if (i == lenb || strs[0].charAt(i) != strs[1].charAt(i))
                    break;
                rst += strs[0].charAt(i);
            }
            return rst;
        }
        int nlen = len / 2 + len % 2;
        String cstrs[] = new String[2];
        String nstrs[] = new String[nlen];
        for (i = 0; i < nlen; i++) {
            if (strs[i] == "")
                return "";
            if (i * 2 == len - 1) {
                nstrs[i] = strs[i * 2];
            } else {
                cstrs[0] = strs[i * 2];
                cstrs[1] = strs[i * 2 + 1];
                nstrs[i] = this.longestCommonPrefix(cstrs);
            }
            if (nstrs[i] == "")
                return "";
        }
        return this.longestCommonPrefix(nstrs);
    }
}

C++:

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        int len = strs.length;
        int i = 0;
        if (len == 0)
            return "";
        if (len == 1)
            return strs[0];
        if (len == 2) {
            if (strs[0].equals(strs[1]))
                return strs[0];
            int lena = strs[0].length();
            int lenb = strs[1].length();
            String rst = "";
            for (i = 0; i < lena; i++) {
                if (i == lenb || strs[0].charAt(i) != strs[1].charAt(i))
                    break;
                rst += strs[0].charAt(i);
            }
            return rst;
        }
        int nlen = len / 2 + len % 2;
        String cstrs[] = new String[2];
        String nstrs[] = new String[nlen];
        for (i = 0; i < nlen; i++) {
            if (strs[i] == "")
                return "";
            if (i * 2 == len - 1) {
                nstrs[i] = strs[i * 2];
            } else {
                cstrs[0] = strs[i * 2];
                cstrs[1] = strs[i * 2 + 1];
                nstrs[i] = this.longestCommonPrefix(cstrs);
            }
            if (nstrs[i] == "")
                return "";
        }
        return this.longestCommonPrefix(nstrs);
    }
}

Python:

class Solution:
    # @return a string
    def longestCommonPrefix(self, strs):
        l = len(strs)
        i = 0
        if (l == 0):
            return ""
        elif (l == 1):
            return strs[0]
        elif (l == 2):
            if (strs[0] == strs[1]):
                return strs[0]
            la = len(strs[0])
            lb = len(strs[1])
            rst = ''
            for i in range(la):
                if (i == lb or strs[0][i] != strs[1][i]):
                    break;
                rst += strs[0][i]
            return rst
        else:
            nl = l / 2 + l % 2
            nstrs = []
            for i in range(nl):
                cstrs = []
                tmp = strs[i * 2]
                if (tmp == ''):
                    return ''
                if (i * 2 == l - 1):
                    nstrs.append(tmp)
                else:
                    cstrs.append(tmp)
                    tmp = strs[i * 2 + 1]
                    if (tmp == ''):
                        return ''
                    cstrs.append(tmp)
                    tmp = self.longestCommonPrefix(cstrs)
                    if (tmp == ''):
                        return ''
                    nstrs.append(tmp)
            return self.longestCommonPrefix(nstrs)

本博客所有文章如无特别注明均为原创。作者：Gcaufy
复制或转载请以超链接形式注明转自码疯窝，原文地址 LeetCode 每日一题 — Longest Common Prefix