Write a function to find the longest common prefix string amongst an array of strings.
即給定一個字符串數(shù)組汛闸，找出數(shù)組中所有字符串的最長公共前綴。
解決該問題的算法有多種隆夯，最容易想到的是橫向掃描别伏，思路如下圖：
該算法的時間復(fù)雜度為O(S)，S是所有字符串的總字符數(shù)愧口；空間復(fù)雜度為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;
}
}
如果字符串數(shù)組中有一個字符串很短类茂，使用上面橫向掃描的方法需要很長時間才能將初始公共前綴縮短到最終的結(jié)果，這時使用縱向掃描可以加快求解速度厚骗。該算法的平均時間復(fù)雜度也是O(S)兢哭，空間復(fù)雜度為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];
}
}
本題還有很多其他解法，如果你感興趣提揍，點擊這里查看
