Description

O(S), S is the sum of all characters in all strings

#!/usr/bin/python

def longestCommonPrefix(strs):
        """
        :type strs: List[str]
        :rtype: str
        """
	if len(strs) == 0:
            return ""

        length = len(strs[0])

        for i in xrange(length):
            for s in strs:
                if i == len(s) or s[i] != strs[0][i]:
                    return s[:i]

        return strs[0]

if __name__ == '__main__':
    strs = ["flower","flow","flight"]
    print strs, longestCommonPrefix(strs)

    strs = ["dog","racecar","car"]
    print strs, longestCommonPrefix(strs)

    strs = ["", "b"]
    print strs, longestCommonPrefix(strs)

    strs = []
    print strs, longestCommonPrefix(strs)

			

O(S)

if len(strs) == 0:
            return ""

        common = strs[0];

        for i in xrange(1, len(strs)):
            if len(common) > len(strs[i]):
                current = common
                common = strs[i]
            else:
                current = strs[i]
            for j in xrange(len(common)):
                if common[j] != current[j]:
                    common = common[:j]
                    break

        return common
			

O(S)

def longestCommonPrefix(strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len(strs) == 0:
            return ""

        common = strs[0];

        for i in xrange(1, len(strs)):
            while strs[i].find(common) != 0:
                common = common[:len(common)-1]

        return common