Write a function to find the longest common prefix string amongst an array of strings.
即给定一个字符串数组，找出数组中所有字符串的最长公共前缀。
解决该问题的算法有多种，最容易想到的是横向扫描，思路如下图：
该算法的时间复杂度为O(S)，S是所有字符串的总字符数；空间复杂度为O(1)
代码如下：
public class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs.length == 0)
return "";
String prefix = strs[0]; // 以第一个字符串作为初始前缀
for(int i = 1; i < strs.length; i++) // 向后横向扫描
{
while(strs[i].indexOf(prefix) != 0) // 不以prefix为前缀
{
prefix = prefix.substring(0, prefix.length() - 1); // 缩小prefix
if (prefix.isEmpty())
return "";
}
}
return prefix;
}
}
如果字符串数组中有一个字符串很短，使用上面横向扫描的方法需要很长时间才能将初始公共前缀缩短到最终的结果，这时使用纵向扫描可以加快求解速度。该算法的平均时间复杂度也是O(S)，空间复杂度为O(1)
代码如下：
public class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0)
return "";
for (int i = 0; i < strs[0].length(); i++)
{
char c = strs[0].charAt(i); // 取出当前字符向后纵向扫描
for (int j = 1; j < strs.length; j++)
{
if (strs[j].length() <= i || strs[j].charAt(i) != c) // 当前字符已不属于公共前缀
return strs[0].substring(0, i);
}
}
return strs[0];
}
}
本题还有很多其他解法，如果你感兴趣，点击这里查看
