[Leetcode] Longest Common Prefix

Problem 

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

Algorithm 

Let n = the number of input strains, and k = the string length. 

For i = 1 : length of str

     For j = 1:str.length

           if i > str[j].length || str[0].substring(i,i+1) != str[j].substring(i,i+1)

                 break;

     End

End

If str has a length n and each string has length O(k), the running time = O(n*k). 

Divide-and-Conquer

LCP(str[]) = LCP(LCP(str[left half]), LCP(str[right half])),  where LCP = Longest Common Prefix.

T(n,k) = 2 * T(n/2,k)+O(k)

 T(n,k) = O(k*log(n))

Code