递归查找列表中最长的字符串

Question

编写一个函数recursiveLongestString（lst），该函数将字符串列表作为输入 并返回列表中最长的字符串。您可以假设该列表至少包含一个 元素，不会出现平局。此函数必须以有意义的方式使用递归 方法使用循环或内置max函数的解决方案将不会获得分数。 例如，recursiveLongestString(["a", "bb", "ccc"])返回"ccc"，并且 recursiveLongestString(["hi", "its", "fantastic", "here"])返回 "fantastic"

这是我目前的代码：

def recursiveLongestString(lst):

    if(len(lst)==1):
        return(lst[0])
    else:
        smaller= recursiveLongestString(lst[1:])
        if len(lst[0])<len(lst[1]):
                return smaller
        else:
            return lst[0] + smaller

我知道这是错误的，但似乎找不到解决办法。请帮忙

Answer 1

为了有意义地使用，您可以将列表一分为二，并递归列表的左子集和右子集，以确定两个最长的字符串，然后比较这两个字符串以获得最终结果：

def recursiveLongestString(lst,start=0,end=None):
    if end is None: end = len(lst)-1 # initial range is whole list 
    if start==end: return lst[start] # base condition, stops recursion
    mid = (start+end)//2             # split index
    maxLeft  = recursiveLongestString(lst,start,mid) # longest on the left
    maxRight = recursiveLongestString(lst,mid+1,end) # longest on the rigth
    return maxLeft if len(maxLeft)>len(maxRight) else maxRight


recursiveLongestString(["hi", "its", "fantastic", "here"])

'fantastic'

这样做的好处是，当您的列表有近1000个项目时，不会达到递归深度限制。此外，它不会创建列表内容的任何副本

通过使用默认参数沿递归调用向下传输最长字符串，可以使还原方法更加紧凑：

def recursiveLongestString(L,S=""):
    return recursiveLongestString(L[1:],(L[0],S)[len(S)>len(L[0])]) if L else S

Answer 2

你很接近。在if/else中，您应该只返回单个字符串，因为这是您希望recursive_longest最终返回的字符串。试试这个：

def recursive_longest(lst):
    if len(lst) == 1:
        return lst[0]

    current = lst[0]
    longest = recursive_longest(lst[1:])
    
    if len(current) < len(longest):
        return longest 
    else:
        return current

对您的奖励：您可能还想在开头添加一个额外的if语句，以决定在提供的列表为空时您可以做什么

Answer 3

这里有一个更有效的版本，因为lst[1:]需要线性时间和空间，因此整个过程需要二次时间和空间。这只需要线性时间和空间：

def recursiveLongestString(lst):
    if not lst:
        return ''
    s = lst.pop()
    t = recursiveLongestString(lst)
    lst.append(s)
    return s if len(s) > len(t) else t