算法题: 最长公共前缀 多种思路解法 LeetCode 第14题

题目

查找字符串数组中的最长公共前缀, 如果不存在公共前缀，返回空字符串 “”.

示例 1:

输入: [“flower”,”flow”,”flight”]

输出: “fl”

示例 2:

输入: [“dog”,”racecar”,”car”]

输出: “”

解释: 输入不存在公共前缀。

说明: 所有输入只包含小写字母 a-z 。

我的思路

1. 取出第一个字符串换成参照字符数组
2. 循环参考字符数组的每一个字符
3. 对比相同 不相等返回 相等拼接继续循环

我的代码

执行用时 :1 ms, 在所有 java 提交中击败了87.85%的用户
内存消耗 :37.6 MB, 在所有 java 提交中击败了73.80%的用户

private static String longestCommonPrefix(String[] strs) {
        StringBuilder res = new StringBuilder();
        if (strs.length <= 0) {
            return "";
        }
        char[] chars = strs[0].toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char b = chars[i];
            for (int j = 1; j < strs.length; j++) {
                String s = strs[j];
                if (s.length() <= i || s.charAt(i) != b) {
                    b = 0;
                    return res.toString();
                }
            }
            res.append(b);
        }
        return res.toString();
    }

提供多种思路

1、所求的最长公共前缀子串一定是每个字符串的前缀子串。所以随便选择一个字符串作为标准，把它的前缀串，与其他所有字符串进行判断，看是否是它们所有人的前缀子串。这里的时间性能是O(m*n*m)。

2、列出所有的字符串的前缀子串，将它们合并后排序，找出其中个数为n且最长的子串。时间性能为O(n*m+m*n*log(m*n))

3、纵向扫描：从下标0开始，判断每一个字符串的下标0，判断是否全部相同。直到遇到不全部相同的下标。时间性能为O(n*m)。

4、横向扫描：前两个字符串找公共子串，将其结果和第三个字符串找公共子串……直到最后一个串。时间性能为O(n*m)。

5、借助trie字典树。将这些字符串存储到trie树中。那么trie树的第一个分叉口之前的单分支树的就是所求。

*(多种写法往后补上)

C 语言代码

4ms

char* longestCommonPrefix(char** strs, int strsSize) {

    char* str=(char*)malloc(128);
    memset(str,0,128);
    int i,j=0;
    if(strsSize<=1)
        return *(strs);
    while(1)
    {
        i=0;
        while(i<strsSize-1)
        {
            if(strs[i][j]!=strs[i+1][j])
                return str;
            i++;
        }
        str[j]=strs[0][j];
        j++;
    }
    return str;
}

python 代码

python两种让你拍大腿的解法，时间复杂度你想象不到，短小精悍。 1、利用python的max()和min()，在Python里字符串是可以比较的，按照ascII值排，举例abb， aba，abac，最大为abb，最小为aba。所以只需要比较最大最小的公共前缀就是整个数组的公共前缀

    def longestCommonPrefix(self, strs):
        if not strs: return ""
        s1 = min(strs)
        s2 = max(strs)
        for i,x in enumerate(s1):
            if x != s2[i]:
                return s2[:i]
        return s1