Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
Example 1:
Input: ["flower","flow","flight"]
Output: "fl"
Example 2:Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:All given inputs are in lowercase letters a-z.
本题应有多种解题思路，包括分治法，二叉树等。
Dr_Sean's solution:
class Solution:
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if strs == []: return ""
elif len(strs) == 1: return strs[0]
else:
LCP, k = '', 0
while k < len(strs[0]):
j, status = 1, False
while j < len(strs):
if strs[0][0:k+1] == strs[j][0:k+1]:
status, j = True, j + 1
else:
// j = len(strs) 结束循环， k = len(strs[0]) 结束外层循环
j, k, status = len(strs), len(strs[0]), False
if status:
LCP = strs[0][0:k+1]
k += 1
return LCP
