LeetCode集锦（五） - 第14题 Longest Common Prefix

内容简介：编写一个函数来查找字符串数组中最长的公共前缀字符串。如果没有公共前缀，返回一个空字符串“”。示例1:

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

 If there is no common prefix, return an empty string "". 

 Example 1: 


Input: ["flower","flow","flight"]
Output: "fl"


 Example 2: 


Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.


 Note: 

 All given inputs are in lowercase letters a-z. 

复制代码

翻译:

编写一个函数来查找字符串数组中最长的公共前缀字符串。

如果没有公共前缀，返回一个空字符串“”。

示例1:

输入:[“花”、“流”、“飞行”)

输出:“fl”

示例2:

输入:“狗”,“赛车”,“车”)

输出:”“

说明:输入字符串之间没有公共前缀。

注意:

所有给定的输入都是小写字母a-z。

解题思路

本题思路很简单，我们选定一个字符串（如果是最短的就最好了），然后根据循环，来一个个对比数组里面的字符串，一个个字符判断，来获取最短路径，找到符合条件的公共字符串，在和下一个比较，最终就是结果了

解题方法

第一种解体方法，按照我们的思路来编辑，代码如下

if (strs.length == 0) {
        return "";
    }
    if (strs.length == 1) {
        return strs[0];
    }

    String st = strs[0];
    StringBuilder stringBuilder = new StringBuilder("");
    for (int i = 0; i < st.length(); i++) {
        char s = st.charAt(i);
        for (int m = 1; m < strs.length; m++) {
            if (strs[m].length() <= i || strs[m].charAt(i) != s) {
                return stringBuilder.toString();
            }
        }
        stringBuilder.append(s);
    }
    return stringBuilder.toString();
复制代码

时间复杂度: 该方案用了循环，循环层数为2，由于第二层判断计数不好记，设为M,外层循环为n,所以f(n)=(n*M)=Mn;所以O(f(n))=O(Mn),即T(n)=O(Mn)

空间复杂度: 该方案没有使用额外的空间，所以空间复杂度是O(1);