2020阿里在线笔试 弹钢琴 最长拼接高昂旋律 Python3

2020阿里在线笔试 弹钢琴 最长拼接高昂旋律 Python3

2020阿里在线笔试 弹钢琴 最长拼接高昂旋律

• 题目描述：
• 示例：
• • 输入：
  • 输出：
• 代码

题目描述：

钢琴有26个键，标为a-z，小强学了N个高昂旋律（不降序列），拼接成最长高昂旋律，求拼接成的最长高昂旋律长度
条件： 0 <= N <= 1e6 ,并且所有字符串长度之和 <= 1e6
输入：第一行：N 接下来N行每行一个不降字符串
输出：一个整数

示例：

输入：

	4aaabcdzzzbcdef

输出：

	11

代码

def dfs(str_begin, list1):if len(list1) == 0:return 0else:while (list1 and list1[0][0] < str_begin):del list1[0]                           #删除第一项，后面依次前移res = 0for i in range(len(list1)):res = max(res, dfs(list1[i][-1],list1[i+1:])+len(list1[i]))    #新的list1要从本次选择项的下一项开始# 注：使用list[n:]不会发生索引溢出return res
'''
N = int(input().strip())
xuanlv_list = []
for _ in range(N):xuanlv_list.append(str(input().strip()))
'''
N = 7
xuanlv_list = ['v','ad','qy','dfs','z','a','zzz']
xuanlv_list = sorted(xuanlv_list)                   #字符串列表升序排序
print(dfs('a',xuanlv_list))