怎样才能找到最长的升序子串（或并列子串）？

Question

如何定义递归样式函数findmax，其工作原理如下：

findmax('abc')-->['abc']
findmax('afz')-->['afz']
findmax('cba')-->['c','b','a']
findmax('zfa')-->['z','f','a']
findmax('abczabc')-->['abcz']
findmax('abcabc')-->['abc','abc']

该函数只显示一个或多个a-z字符。并返回所有按升序排列的最长子字符串。在

我为什么问这个问题？因为我的直觉告诉我一定有一个优雅的回避式的解决方案。但遗憾的是，我无法解决。在

请看看我写的可怕的解决方案：

^{pr2}$

Answer 1

下面是一个递归的解决方案。此函数是纯递归的，没有for循环，更确切地说，根本没有循环：

def find_max(s):
    _ret = []

    def string_iter(concat, compare):

        def appender():
            if len(concat) >= len(_ret[-1]):
                if len(concat) > len(_ret[-1]):
                    while _ret:
                        _ret.pop()
                _ret.append(concat)

        if len(compare) == 0:
            if len(_ret) != 0:
                appender()
            else:
                _ret.append(concat)
            return

        if concat[-1] < compare[0]:
            concat += compare[0]
            string_iter(concat, compare[1:])
        else:
            if len(_ret) != 0:
                appender()
            else:
                _ret.append(concat)
            string_iter(compare[0], compare[1:])

    string_iter(s[0], s[1:])

    return _ret

print find_max('abc')      # -->['abc']
print find_max('afz')      # -->['afz']
print find_max('cba')      # -->['c','b','a']
print find_max('zfa')      # -->['z','f','a']
print find_max('abczabc')  # --> ['abcz']
print find_max('abcabcpaidfbkjabdsfilabdfkabldfjadf')   # --> ['abcp', 'abdfk']

Answer 2

如果你真的想要一个递归风格的函数。我不知道它是否更优雅，但我知道它比命令式（递归限制和尾部调用）更不有效，也更受限制：

from collections import defaultdict

'''
    Return the "biggest" key (assuming keys are int).
    Should've used a ordered set instead of a dict
'''
def maxkey(dictio):
    return max ([ int(k) for k in dictio.keys() ])

'''
    Recursion-style of findmax. Notice the call to the same input string minus the first element,
    which indicate that the recursion isn't really much more efficient than imperative style.
    Also we have to take the maximum recursion limit into account (which should be attained in practice.)
'''
def findmax( input_string , tempbuffer = defaultdict(list), temp = '' ):

    # End of the recursion
    if len(input_string) == 0:
        tempbuffer[len(temp)].append(temp)          # add last element
        output = tempbuffer[maxkey(tempbuffer)]     # return the set of longest elements
        tempbuffer.clear()                          # pesky little mutable objects ...
        return output

    # Still elements in the input string
    else:
        first_char = input_string[0]

        # still ascending : buffering
        if len(temp) == 0 or first_char > temp[-1]:
            temp   = temp + first_char
        # new string : store the old one
        else:
            tempbuffer[len(temp)].append(temp)
            temp   = first_char

        # Recursion call on the 'tail' of the input string, one character at a time
        return findmax( input_string[1:],tempbuffer, temp)




if __name__ == '__main__' :

    print findmax('abczabc')

    print findmax('abcabd')

Answer 3

根本不需要递归。在

def findmax(s):
    matches = []
    current = [s[0]]
    for index, character in enumerate(s[1:]):
        if character >= s[index]:
            current.append(character)
        else:
            matches.append(current)
            current = [character]
    matches.append(current)
    maxlen = len(max(matches, key=len))
    return ["".join(match) for match in matches if len(match)==maxlen]

测试用例：

^{pr2}$

Explanation can be found here（对该代码稍作修改）。在