Description

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 “”.

1
2
3
4
Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"
1
2
3
4
5
Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
1
2
3
4
5
Constraints:

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lowercase English letters if it is non-empty.

Approach

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        
        if len(strs)==1:
            return strs[0]

        s1 = strs[0]
        result = ""
        endFlag = False
        for inner in range(len(s1) + 1):
            sub = s1[0:inner]
            for out in range(1, len(strs)):
                if strs[out].startswith(sub):
                    if len(result) < len(sub) and out == len(strs)-1:
                        result = sub
                else:
                    endFlag = True
                    break
            if endFlag:
                break
        return result
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def longestCommonPrefix(self, v: List[str]) -> str:
        ans=""
        v=sorted(v)
        first=v[0]
        last=v[-1]
        for i in range(min(len(first),len(last))):
            if(first[i]!=last[i]):
                return ans
            ans+=first[i]
        return ans