Longest Common Prefix

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

Understand the problem:
The question asks for finding the longest common prefix (LCP) string among an array of strings. We can take an example to illustrate this problem. For the array of strings
a
bc
cd
The LCP string is empty as there is no common prefix at all.

For the array of strings
a
ab
abc
The LCP string is "a" since a is the longest common prefix string

For an array of strings
abc
abd
abfghi
The LCP string is "ab" since it is the longest common prefix string.

Solution:
Based on the analysis above, we can come up a solution. We compare the character with the same index for each of the string. If the same, we go to the next. There are two termination conditions:
a. the LCP is the shortest string, as in the example 2. 
b. the LCP is the substring of a string, we continue until we found the character is different. 

Code (Java):

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        
        for (int i = 0; i < strs[0].length(); i++) {
            for (int j = 0; j < strs.length - 1; j++) {
                if (i >= strs[j].length() || i >= strs[j + 1].length() || strs[j].charAt(i) != strs[j + 1].charAt(i)) {
                    return strs[j].substring(0, i);
                }
            }
        }
        return strs[0];
    }
}

Discussion:
The time complexity of this solution is O(m * n), where m is the length of the LCP string, n is the number of strings in the array.

Summary:
It is not a very difficult question, but requires careful implementation. Note the outer loop, where i < strs[0].length(). Think about why we choose to use strs[0].length() ? Actually what we wanna find is the LCP string. So if strs[0] itself is the LCP string, it is fine. If strs[0] is not, we have other conditions inside of the loop to terminate the loop. How about we choose strs[1]? It is basically correct, however be careful about the size of the array, which has only one element. So we must change the code slightly like this:

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        if (strs.length == 1) return strs[0];
        
        for (int i = 0; i < strs[1].length(); i++) {
            for (int j = 0; j < strs.length - 1; j++) {
                if (i >= strs[j].length() || i >= strs[j + 1].length() || strs[j].charAt(i) != strs[j + 1].charAt(i)) {
                    return strs[j].substring(0, i);
                }
            }
        }
        return strs[1];
    }
}

Update on 9/28/15:

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        
        StringBuffer sb = new StringBuffer();
        
        for (int i = 0; i < strs[0].length(); i++) {
            char curr = strs[0].charAt(i);
            int j = 1;
            for (j = 1; j < strs.length; j++) {
                String str = strs[j];
                if (str == null || str.length() == 0 || i >= str.length() || str.charAt(i) != curr) {
                    break;
                }
            }
            if (j == strs.length) {
                sb.append(curr);
            } else {
                break;
            }
        }
        
        return sb.toString();
    }
}