python - 如何找到最长的升序子串（或绑定子串）？

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']

该函数仅接收一个或多个 az 字符。并返回字符按升序排列的所有最长子字符串。

我为什么要问这个问题？因为我的直觉告诉我必须有一个优雅的回溯式解决方案。但很遗憾，我无法解决。

请看看我写的糟糕的解决方案：

def findmax(s):
    res=[]
    string=s[0]
    end=len(s)
    for i in range(1,end):
        if ord(s[i-1])<=ord(s[i]):
            string+=s[i]
            if i==end-1:
                res.append(string)                
        else:
            res.append(string)
            string=s[i]
            if i==end-1:
                res.append(string)
    fin=[]
    maxNum=0
    for r in res:
        size=len(r)
        if size>maxNum:
            maxNum=size
            fin=[]
            fin.append(r)
        elif size==maxNum:
            fin.append(r)                    
    return fin

Answer 1

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

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 2

以下是递归解决方案。这个函数是纯递归的，没有 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 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]

测试用例：

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

可以在此处找到说明（此代码的略微修改版本）。

Answer 4

使我的解决方案适应以前的答案：

import string

def findmax(s):
    groups = []
    cur_longest = ''
    prev_char = ''
    for c in map(string.lower, s):
        if prev_char and c < prev_char:
            groups.append(cur_longest)
            cur_longest = c
        else:
            cur_longest += c
        prev_char = c
    groups.append(cur_longest)
    length = max([len(g) for g in groups])
    return [group for group in groups if len(group) == length]

使用它：

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

Answer 5

在研究了 georgesl 和 Games Brainiac 的两个答案后，我得到了一个更满意的解决方案，结合了它们的两个优点。

两者在结构上都设计得很好。

我认为georgesl的优势在于： tempbufferdict对象的设计，而Games Brainiac的优势在于：closure.

虽然效果较差，但我仍然很高兴确实存在一个简单而优雅的解决方案。

所以，在这里我想分享：

from collections import defaultdict

def findmax(s):
    buf=defaultdict(list)
    def recur(s,mbr):
        if s=='':
            buf[len(mbr)].append(mbr)
            return buf[max(buf)]
        else:
            head=s[0]
            if mbr=='' or mbr[-1]<head:
                mbr=mbr+head
            else:
                buf[len(mbr)].append(mbr)
                mbr=head
            return recur(s[1:],mbr)
    return recur(s,'')

if __name__ == '__main__' :
    print 'abc',findmax('abc')
    print 'afz',findmax('afz') 
    print 'abcabcda',findmax('abcabcda')
    print 'abczabcdabcd',findmax('abczabcdabcd')               
    print 'zfa',findmax('zfa')
    print 'zfa',findmax('zfa')

结果如下：

>>> 
abc ['abc']
afz ['afz']
abcabcda ['abcd']
abczabcdabcd ['abcz', 'abcd', 'abcd']
zfa ['z', 'f', 'a']
zfa ['z', 'f', 'a']