14. Longest Common Prefix

题目描述：

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

题目翻译

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

解题方案

标签： String

思路：

• 为了较好的理解题意，举个栗子

String[] strs = {
    "abcdiefgi",
    "abcdefghijk",
    "abcdfghijk",
    "abcef"
}

上面的字符串数组的最长公共前缀就是"abc"。

• 具体算法为：取出第一个字符串初始化为公共前缀。
• 遍历字符串数组，每个字符串再与公共前缀取公共前缀，比如"abcdiefgi"与"abcdefghijk"公共前缀为"abcd"
• 直到公共前缀为空结束循环，或者遍历结束，返回最终结果
• 时间复杂度O(n)

代码：

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.substring(0, prefix.length() - 1);
            if (prefix.isEmpty()) return "";
        }        
    return prefix;
}

参考资料

http://blog.csdn.net/zhning12L/article/details/78198119