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.

 

这道题让我们求一系列字符串的共同前缀，没有什么特别的技巧，无脑查找即可，我们定义两个变量i和j，其中i是遍历搜索字符串中的字符，j是遍历字符串集中的每个字符串。这里将单词上下排好，则相当于一个各行长度有可能不相等的二维数组，我们遍历顺序和一般的横向逐行遍历不同，而是采用纵向逐列遍历，在遍历的过程中，如果某一行没有了，说明其为最短的单词，因为共同前缀的长度不能长于最短单词，所以此时返回已经找出的共同前缀。我们每次取出第一个字符串的某一个位置的单词，然后遍历其他所有字符串的对应位置看是否相等，如果有不满足的直接返回res，如果都相同，则将当前字符存入结果，继续检查下一个位置的字符，参见代码如下：

 

C++ 解法一：

class Solution {public:    string longestCommonPrefix(vector
     
      & strs) {        if (strs.empty()) return "";        string res = "";        for (int j = 0; j < strs[0].size(); ++j) {            char c = strs[0][j];            for (int i = 1; i < strs.size(); ++i) {                if (j >= strs[i].size() || strs[i][j] != c) {                    return res;                }            }            res.push_back(c);        }        return res;    }};
     

 

Java 解法一：

public class Solution {    public String longestCommonPrefix(String[] strs) {        if (strs == null || strs.length == 0) return "";        String res = new String();        for (int j = 0; j < strs[0].length(); ++j) {            char c = strs[0].charAt(j);            for (int i = 1; i < strs.length; ++i) {                if (j >= strs[i].length() || strs[i].charAt(j) != c) {                    return res;                }            }            res += Character.toString(c);        }        return res;    }}

 

我们可以对上面的方法进行适当精简，如果我们发现当前某个字符和下一行对应位置的字符不相等，说明不会再有更长的共同前缀了，我们直接通过用substr的方法直接取出共同前缀的子字符串。如果遍历结束前没有返回结果的话，说明第一个单词就是公共前缀，返回为结果即可。代码如下：

 

C++ 解法二：

class Solution {public:    string longestCommonPrefix(vector
     
      & strs) {        if (strs.empty()) return "";        for (int j = 0; j < strs[0].size(); ++j) {            for (int i = 0; i < strs.size() - 1; ++i) {                if (j >= strs[i].size() || j >= strs[i + 1].size() || strs[i][j] != strs[i + 1][j]) {                    return strs[i].substr(0, j);                }            }        }        return strs[0];    }};
     

 

Java 解法二：

public class Solution {    public String longestCommonPrefix(String[] strs) {        if (strs == null || strs.length == 0) return "";        for (int j = 0; j < strs[0].length(); ++j) {            for (int i = 0; i < strs.length - 1; ++i) {                if (j >= strs[i].length() || j >= strs[i + 1].length() || strs[i].charAt(j) != strs[i + 1].charAt(j)) {                    return strs[i].substring(0, j);                   }            }        }        return strs[0];    }}

 

我们再来看一种解法，这种方法给输入字符串数组排了个序，想想这样做有什么好处？既然是按字母顺序排序的话，那么有共同字母多的两个字符串会被排到一起，而跟大家相同的字母越少的字符串会被挤到首尾两端，那么如果有共同前缀的话，一定会出现在首尾两端的字符串中，所以我们只需要找首尾字母串的共同前缀即可。比如例子1排序后为 ["flight", "flow", "flower"]，例子2排序后为 ["cat", "dog", "racecar"]，虽然例子2没有共同前缀，但也可以认为共同前缀是空串，且出现在首尾两端的字符串中。由于是按字母顺序排的，而不是按长度，所以首尾字母的长度关系不知道，为了防止溢出错误，我们只遍历而这种较短的那个的长度，找出共同前缀返回即可，参见代码如下：

 

C++ 解法三：

class Solution {public:    string longestCommonPrefix(vector
     
      & strs) {        if (strs.empty()) return "";        sort(strs.begin(), strs.end());        int i = 0, len = min(strs[0].size(), strs.back().size());        while (i < len && strs[0][i] == strs.back()[i]) ++i;        return strs[0].substr(0, i);    }};
     

 

Java 解法三：

class Solution {    public String longestCommonPrefix(String[] strs) {        if (strs == null || strs.length == 0) return "";        Arrays.sort(strs);        int i = 0, len = Math.min(strs[0].length(), strs[strs.length - 1].length());        while (i < len && strs[0].charAt(i) == strs[strs.length - 1].charAt(i)) i++;        return strs[0].substring(0, i);    }}

 

参考资料：