Why isn't my return command being obeyed?

Question

I'm trying to write a function to return the longest common prefix from a series of strings. Using a debugger, saw that my function reaches the longest common prefix correctly, but then when it reaches the statement to return, it begins reverting to earlier stages of the algorithm.

For test case strs = ["flower","flow","flight"]

The output variable holds the following values:-

f > fl > f

instead of returning fl.

Any help would be appreciated, because I don't really know how to Google for this one. Thank you.

class Solution(object):
def longestCommonPrefix(self, strs, output = ''):
    #return true if all chars in string are the same
    def same(s):
        return s == len(s) * s[0]
    
    #return new list of strings with first char removed from each string
    def slicer(list_, list_2 = []):
        for string in list_:
            string1 = string[1:]
            list_2.append(string1)
        return list_2
    
    #return string containing first char from each string
    def puller(list_):
        s = ''
        for string in list_:
            s += string[0]
        return s
    
    #pull first character from each string
    s = puller(strs)
    
    #if they are the same
    #add one char to output
    #run again on sliced list
    if same(s):
        output += s[0]
        self.longestCommonPrefix(slicer(strs), output)            
    
    return output

Answer 1

This can be handled with os.path.commonprefix.

>>> import os
>>> strs = ["flower","flow","flight"]
>>> os.path.commonprefix(strs)
'fl'

Answer 2

It doesn't "revert". longestCommonPrefix potentially calls itself - what you're seeing is simply the call-stack unwinding, and flow of execution is returning to the calling code (the line that invoked the call to longestCommonPrefix from which you are returning).

That being said, there's really no need to implement a recursive solution in the first place. I would suggest something like:

def get_common_prefix(strings):

    def get_next_prefix_char():
        for chars in zip(*strings):
            if len(set(chars)) != 1:
                break
            yield chars[0]

    return "".join(get_next_prefix_char())


print(get_common_prefix(["hello", "hey"]))

Answer 3

You are looking at the behavior...the final result...of recursive calls to your method. However, the recursive calls don't do anything to affect the result of the initial execution of the method. If we look at the few lines that matter at the end of your method:

if same(s):
    output += s[0]
    self.longestCommonPrefix(slicer(strs), output)            

return output

The problem here is that since output is immutable, its value won't be changed by calling longestCommonPrefix recursively. So from the standpoint of the outermost call to longestCommonPrefix, the result it will return is determined only by if same(s) is true or false. If it is true it will return s[0], otherwise it will return ''.

The easiest way to fix this behavior and have your recursive call affect the result of the prior call to the method would be to have its return value become the value of output, like this:

if same(s):
    output += s[0]
    output = self.longestCommonPrefix(slicer(strs), output)            

return output

This is a common code pattern when using recursion. Just this change does seem to give you the result you expect! I haven't analyzed your whole algorithm, so I don't know if it becomes "correct" with just this change.

Answer 4

Can you try this? I

class Solution(object):
def longestCommonPrefix(self, strs, output = ''):
    #return true if all chars in string are the same
    def same(s):
        return s == len(s) * s[0]
    
    #return new list of strings with first char removed from each string
    def slicer(list_, list_2 = []):
        for string in list_:
            string1 = string[1:]
            list_2.append(string1)
        return list_2
    
    #return string containing first char from each string
    def puller(list_):
        s = ''
        for string in list_:
            s += string[0]
        return s
    
    #pull first character from each string
    s = puller(strs)
    
    # Can you Try this revision? 
    # I think the problem is that your new version of output is being lost when the fourth called function returns to the third and the third returns to the second, etc...
    # You need to calculate a new output value before you call recursively, that is true, but you also need a way to 'store' that output when that recursively called function 'returns'.  Right now it disappears, I believe.
    if same(s):  
        output += s[0]
        output = self.longestCommonPrefix(slicer(strs), output)            

    return output