Longest Common Prefix 78

Question

Given k strings, find the longest common prefix (LCP).

Example

For strings "ABCD", "ABEF" and "ACEF", the LCP is "A"

For strings "ABCDEFG", "ABCEFG" and "ABCEFA", the LCP is "ABC"

Solution

这道题就是依次比较每一个字符串，找到所有字符串最长的公共字串。可以先假设第一个字符串为最长公共字串，然后用它和其他字符串逐位比较，找到最长的公共字串，并更新最长公共字串，直到和所有字符串比较过为止。在这个过程中吗，只要有任何两个字符串的公共字串长度为0，即返回""。

代码如下：

public class Solution {
    /**
     * @param strs: A list of strings
     * @return: The longest common prefix
     */
    public String longestCommonPrefix(String[] strs) {
        // write your code here
        if(strs == null || strs.length == 0){
            return "";
        }

        String lcp = strs[0];
        for(int i = 0; i < strs.length; i++){
            int j = 0;
            while(j < strs[i].length() && j < lcp.length() && strs[i].charAt(j) == lcp.charAt(j)){
                j++;
            }
            if(j == 0){
                return "";
            }
            lcp = lcp.substring(0, j);
        }

        return lcp;
    }
}