14 Longest Common Prefix

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: strs = ["flower","flow","flight"]
Output: "fl"
``````

Example 2:

``````Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
``````

Constraints:

• `1 <= strs.length <= 200`
• `0 <= strs[i].length <= 200`
• `strs[i]` consists of only lowercase English letters.
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 `````` ``````class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: pre = strs[0] for i in range(1, len(strs)): while not strs[i].startswith(pre): pre = pre[:-1] return pre ''' Sort first ''' class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: strs.sort() res = strs[0] # only check with the last one while not strs[-1].startswith(res): res = res[:-1] return res``````
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 `````` ``````/* Sort and reduce prefix */ func longestCommonPrefix(strs []string) string { sort.Strings(strs) res := strs[0] for !strings.HasPrefix(strs[len(strs)-1], res) { res = res[:len(res)-1] } return res } /* Sort and compare first & last */ func longestCommonPrefix(strs []string) string { sort.Strings(strs) first := strs[0] last := strs[len(strs)-1] for i := range first { if first[i] != last[i] { return first[:i] } } return first }``````