Longest Common Prefix from list elements in Python-CodePudding

I have a list as below:

strs = ["flowers", "flow", "flight"]

Now, I want to find the longest prefix of the elements from the list. If there is no match then it should return "". I am trying to use the 'Divide and Conquer' rule for solving the problem. Below is my code:

strs = ["flowers", "flow", "flight"]

firstHalf = ""
secondHalf = ""


def longestCommonPrefix(strs) -> str:
    minValue = min(len(i) for i in strs)
    length = len(strs)
    middle_index = length // 2
    firstHalf = strs[:middle_index]
    secondHalf = strs[middle_index:]
    minSecondHalfValue = min(len(i) for i in secondHalf)
    matchingString=[] #Creating a stack to append the matching characters
    for i in range(minSecondHalfValue):
        secondHalf[0][i] == secondHalf[1][i]
    return secondHalf


print(longestCommonPrefix(strs))

I was able to find the mid and divide the list into two parts. Now I am trying to use the second half and get the longest prefix but am unable to do so. I have had created a stack where I would be adding the continuous matching characters and then I would use it to compare with the firstHalf but how can I compare the get the continuous matching characters from start?

Expected output:

"fl"

Just a suggestion would also help. I can give it a try.

CodePudding user response：

No matter what, you need to look at each character from each string in turn (until you find a set of corresponding characters that doesn't match), so there's no benefit to splitting the list up. Just iterate through and break when the common prefix stops being common:

def common_prefix(strs) -> str:
    prefix = ""
    for chars in zip(*strs):
        if len(set(chars)) > 1:
            break
        prefix  = chars[0]
    return prefix


print(common_prefix(["flowers", "flow", "flight"]))  # fl

CodePudding user response：

Sort of "divide and conquer" :

solve for 2 strings
solve for the other strings

def common_prefix2_(s1: str, s2: str)-> str:
    if not s1 or not s2: return "" 
    for i, z in enumerate(zip(s1,s2)):
        if z[0] != z[1]:
            break
    else:
        i  = 1
    return s1[:i]

from functools import reduce
def common_prefix(l:list):
    return reduce(common_prefix2_, l[1:], l[0]) if len(l) else ''

Tests

for l in [["flowers", "flow", "flight"],
          ["flowers", "flow", ""],
          ["flowers", "flow"],
          ["flowers", "xxx"],
          ["flowers" ],
          []]:
    print(f"{l if l else '[]'}: '{common_prefix(l)}'")

# output
['flowers', 'flow', 'flight']: 'fl'
['flowers', 'flow', '']: ''
['flowers', 'flow']: 'flow'
['flowers', 'xxx']: ''
['flowers']: 'flowers'
[]: ''