Longest Common Prefix

Problem: Longest Common Prefix

Due to the definition of longest common prefix, we can easily implement an iterative solution.

Code in Python:

    class Solution(object):
        def longestCommonPrefix(self, strs):
            """
            :type strs: List[str]
            :rtype: str
            """
            if not len(strs):
                return ""
            lcp, lcpl = strs[0], len(strs[0])
            for s in strs:
                if len(s) >= lcpl and s[:lcpl] == lcp:
                    continue
                if s == "":
                    return ""
                lcp, lcpl = lcp[:min(lcpl, len(s))], min(lcpl, len(s))
                for i, c in enumerate(lcp):
                    if c != s[i]:
                        lcp, lcpl = lcp[:i], i
            return lcp

Code in Java:

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0)
            return "";

        String res = strs[0];
        for (int i = 1; i < strs.length; i++) {
            int j;
            for (j = 0; j < Math.min(res.length(), strs[i].length()); j++)
                if (res.charAt(j) != strs[i].charAt(j))
                    break;
            res = res.substring(0,j);
        }
        return res;
    }
}

However, it's not necessary to iterate through all the strings the same time when we check all the single characters. We can first find the minimum length of a string. Then we check all the characters located on first position of all the strings. Thus, the running time will definitely be n*k, where k is our answer, while running time of the previous solutions are bigger than that. Such a solution can be found here.