如何求解字符串中字典序最大的子序列
版权申诉
47 浏览量
2020-12-20
19:17:16
上传
评论
收藏 51KB PDF 举报
如何求解字符串中字典序最大的子序列如何求解字符串中字典序最大的子序列
问题描述问题描述
给定一个字符串,求字符串中字典序最大的子序列.字典序最大的子序列是这样构造的:给定一个字符串 a0a1…an−1a_{0}a_{1}
…a_{n-1}a0a1…an−1 ,首先在字符串中找到值最大的字符 aia_{i}ai,然后在剩余的字符串 ai+1ai+2…ana_{i+1}a_{i+2}…
a_{n}ai+1ai+2…an中找到值最大的字符aja_{j}aj,然后在剩余的字符串aj+1aj+2…ana_{j+1}a_{j+2}…a_{n}aj+1aj+2…an中找到
值最大的字符aka_{k}ak, ………………一直这样做下去,直到剩余字符串的长度为0为止.找到的字符按找到的顺序排成的字符串
aiajak…a_{i}a_{j}a_{k}…aiajak…就是我们要找的答案.
分析与解答分析与解答
这个题目要解决,就得了解字典序的概念.题目已经讲得比较明白了,所以一个很自然的想法,就是要多次遍历这个字符串,每一次
找到字符串中的第一次出现的最大的元素,提取出来,将这个最大的元素的后缀作为下一次要遍历的字符串,同样地找到它最大的
元素,不断这样遍历下去,就可以得到我们想要的字典序最大的子序列了.每次遍历得到的元素需要被保存,用largestSubStr来保
存最后的字符串.
#给定一个字符串,求字符串中字典序最大的子序列.
def getLargestSubStr(strs):
if strs == None:
return
largestSubStr = ""
while len(strs) > 0:
lens = len(strs)
#最大数临时变量
maxNum = -1
#最大数下标临时变量
maxIndex = 0
for i in range(lens):
if ord(strs[i]) > maxNum:
maxNum = ord(strs[i])
maxIndex = i
largestSubStr += strs[maxIndex] strs = strs[maxIndex+1:] return largestSubStr
if __name__ == "__main__":
strs = "cdffgjkjlmnoopchd"
lstrs = getLargestSubStr(strs)
print("原始字符串为:", str(strs))
print("字典序最大的子序列为:", str(lstrs))
原创文章 12获赞 12访问量 368
关注
私信
展开阅读全文
作者：@lonely
资源评论
