美文网首页
最长连续递增字符串

最长连续递增字符串

作者: BlueSkyBlue | 来源:发表于2018-05-30 21:13 被阅读16次

题目:

输入一段字符串(由字母构成),找出这段字符串中连续的最长的递增字符。

举例:
字符串:eahcu
结果:acu, ahu, ehu


思路:

本题有两种思路求解,一种是递归的形式,首先找到最后一位字符,将其加入到结果集中,然后需要进行两步查找:

一步是找大于结果集中第一位字符的字符,并将该字符加入到结果集中。

另一步是将小于结果集中第一位字符的字符加入到结果集中指定的字符串中,从而更新结果集。

还有一种方法是动态规划的方法。
动态规划最重要的就是找到状态方程和状态数组。状态数组中每个数字代表的意义是从字符串首位到当前字符递增序列的最长长度。之后是状态方程,一旦发现当前字符大于之前的某个字符则更新当前字符的状态值,更新为大于的字符的状态值加上1。

在更新状态值的过程中也需要更新子字符串。一旦当前字符大于之前的某个字符ch,则更新子字符,将所有状态值小于当前字符状态值的子字符串加上当前字符。最后取长度最大的子字符串。


代码:

递归:

def longestConsective(str):
    if len(str) == 1:
        return {str}
    results = longestConsective(str[1:])
    solution = set(results)
    if all(chr[0] < str[0] for chr in results):
        solution.add(str[0])
    solution.update(str[0] + chr for chr in results if str[0] < chr[0])
    return solution

if __name__ == '__main__':
    str = input('Please input the string: ')
    results = longestConsective(str)
    max_len = max(len(str) for str in results)
    ares = sorted(result for result in results if len(result) == max_len)
    print(ares)

动态规划:

def dplongestConsective(str):
    '''
    Find longest consecutive string by dynamic programming.
    :param str: 
    :return: 
    '''
    if not str:
        return ''
    solution = [(1, {str[i]}) for i in range(len(str))]
    max_length = 1
    for i in range(1, len(str)):
        length_so_far = 1
        for j in range(i):
            length, good_words = solution[j]
            if length < length_so_far - 1:
                continue
            if str[j] > str[i]:
                continue
            if length == length_so_far - 1:
                solution[i][1].update(w + str[i] for w in good_words)
            else:
                length_so_far = length + 1
                solution[i] = length_so_far, {w + str[i] for w in good_words}
            max_length = max(max_length, length_so_far)
    return sorted(w for (length, set_of_words) in solution if length == max_length
                  for w in set_of_words)

相关文章

网友评论

      本文标题:最长连续递增字符串

      本文链接:https://www.haomeiwen.com/subject/cqtgjftx.html