Data-Structures-and-Algorithm/Data-Structures/String/longest-common-prefix.py at main · shradhaagarwal01/Data-Structures-and-Algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#Brute Force - Horizontal Scanning

def longestCommonPrefix(self, strs: List[str]) -> str:
    if len(strs)==0:
        return ""
    prefix = strs[0]
    for i in range(1,len(strs)):
        while(prefix!=strs[i][:len(prefix)] and len(prefix)>0):
            prefix = prefix[0:-1]
    return prefix

#<------------------------------------------------------------------->

#Better - Vertical Scanning

def longestCommonPrefix(self, strs: List[str]) -> str:
    if len(strs)==0:
        return ""
    for i in range(len(strs[0])):
        c = strs[0][i]
        for j in range(1,len(strs)):
            if i==len(strs[j]) or strs[j][i]!=c:
                return strs[0][:i]
    return strs[0]

#<------------------------------------------------------------------->

#Optimal - By sorting

def longestCommonPrefix(self, strs: List[str]) -> str:
    if len(strs)==0:
        return ""
    strs.sort()
    prefix = ""
    for i in range(len(strs[0])):
        if strs[0][i]!=strs[-1][i]:
            break
        prefix = prefix+strs[0][i]
    return prefix