FilesExpand file tree

 master

/

longest_common_prefix.py

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

35 lines (28 loc) · 1.07 KB

 master

/

longest_common_prefix.py

Top

File metadata and controls

• Code
• Blame

35 lines (28 loc) · 1.07 KB

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

#!/usr/bin/env python

'''

Leetcode: Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

'''

from __future__ import division

import random

### Solution#1: Build a trie tree: O(nm)

### Solution#2: Hash the first string as f, fl, flo, flow, flowe, flower, and initialize the max_prefix_len=5.

# For every other string s, start checking the prefix with min{max_prefix_len, len(s)}. If match go to the next string; if not, remove the last character and re-compare. ~O(n+m)

def longest_prefix(strings):

first = strings[0]

prefixs = set([first[:i] for i in range(len(first))])

max_prefix_len = len(first)

i = 1

while i < len(strings) and max_prefix_len > 0:

s = strings[i]

# Adjust the length

l = min(len(s), max_prefix_len)

s = s[:l]

max_prefix_len = l

while s not in prefixs:

s = s[:-1]

max_prefix_len -= 1

i += 1

return first[:max_prefix_len]

if __name__ == '__main__':

print longest_prefix(['hello','hell','heaven','heavy'])