LeetCode 14 - Longest Common Prefix

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

Solution 1:

比较每个字符串的第一个字符，然后第二个。。。。出现不同的字符的话，马上返回结果，如果所有字符串的第i个字符都相等，则把这个字符append到结果上去。

public String longestCommonPrefix(String[] strs) {
    if(strs == null || strs.length<1) return "";
    StringBuilder sb = new StringBuilder();
    for(int i=0; i<strs[0].length(); i++) {
        char ch = strs[0].charAt(i);
        for(int j=1; j<strs.length; j++) {
            if(i>=strs[j].length() || ch != strs[j].charAt(i)) {
                return sb.toString();
            }
        }
        sb.append(ch);
    }
    return sb.toString();
}

 

重构了下代码：

public String longestCommonPrefix(String[] strs) {
    if(strs.length == 0) return "";
    StringBuilder sb = new StringBuilder(strs[0]);
    for(int i=0; i<sb.length(); i++) {
        for(int j=1; j<strs.length; j++) {
            if(i >= strs[j].length() || strs[0].charAt(i) != strs[j].charAt(i)) {
                return sb.substring(0, i);
            }
        }
    }
    return sb.toString();
}

 

Solution 2:

 

public String longestCommonPrefix(String[] strs) {
    if(strs == null || strs.length<1) return "";
    String prefix = strs[0];
    int end = prefix.length();
    for(String s:strs) {
        end = Math.min(end, s.length());
        while(!s.startsWith(prefix.substring(0, end))) {
            end--;
            if(end <= 0) return "";
        }
    }
    return prefix.substring(0, end);
}