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:

 12 Input: ["flower","flow","flight"] Output: "fl" 

Example 2:

 123 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.

Related Topics: String

## 解題邏輯與實作

 12345678910111213141516171819202122232425262728293031 class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: if not strs: return "" strs.sort() return self.LCP(strs) def LCP(self, strs): total_str = len(strs) prefix = "" if total_str == 1 : prefix = strs[0] elif total_str == 2 : if len(strs[0]) < len(strs[1]) : prefix = strs[0] compared = strs[1] else: prefix = strs[1] compared = strs[0] while prefix not in compared[:len(prefix)] and len(prefix)>0 : prefix = prefix[:len(prefix)-1] else: half= total_str // 2 prefix = self.LCP([self.LCP(strs[:half]), self.LCP(strs[half:])]) return prefix 

 12345678910111213 class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: if not strs: return "" strs.sort(key = lambda i:len(i),reverse=False) prfix = strs[0] for i, c in enumerate(prfix): for s in strs: if c != s[i] : return prfix[:i] return prfix