FilesExpand file tree

master

/

longest-common-prefix.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

36 lines (30 loc) · 897 Bytes

master

/

longest-common-prefix.py

Copy path

Top

File metadata and controls

• Code
• Blame

36 lines (30 loc) · 897 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

# Time: O(n * k), k is the length of the common prefix

# Space: O(1)

class Solution(object):

def longestCommonPrefix(self, strs):

"""

:type strs: List[str]

:rtype: str

"""

if not strs:

return ""

for i in xrange(len(strs[0])):

for string in strs[1:]:

if i >= len(string) or string[i] != strs[0][i]:

return strs[0][:i]

return strs[0]

# Time: O(n * k), k is the length of the common prefix

# Space: O(k)

class Solution2(object):

def longestCommonPrefix(self, strs):

"""

:type strs: List[str]

:rtype: str

"""

prefix = ""

for chars in zip(*strs):

if all(c == chars[0] for c in chars):

prefix += chars[0]

else:

return prefix

return prefix