14 Longest Common Prefix

🔀 Pick One

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
}