longestcommonprefix - all combos.py

def longestCommonPrefix(strs: List[str]) -> str:
    if len(strs) == 0 : 
        return ""

    maxlen = len(sorted(strs,key = len)[0])
    output = "" #longest common prefix

    for i in range(maxlen):
        ch = [word[i] for word in strs] # for each next char in the prefix
        if ch.count(ch[0]) == len(ch): # this checks that 'c' occurs 3 times for three words, n times for 
            output += str(ch[0]) # appending to the longest common prefix
        else:
            return output # This returns the prefix up till the i-1th character. if the ith character does not match, then it will return the prefix uptil the i-1th char
    return output

def longestAllCombos(strs):
    import itertools
    output = []
    for windowsize in range(2, len(strs)):
        allCombos = [p for p in itertools.combinations(strs,windowsize)]
        for combo in allCombos:
            print("combination")
            print(list(combo))
            print("LCP")
            lcp = longestCommonPrefix(list(combo))
            print(lcp)
            if lcp: output.append(lcp)
    
    allsubstrs = []
    for s in output:
        for i in range(len(s)):
            output.append(s[:i])
    
    output = list(set(output))
    return output    
    
    

print(longestAllCombos(["cat","caterpillar","bat","banana"]))