如何求解字符串中字典序最大的子序列

Gella ·

更新时间:2024-09-20

· 955 次阅读

问题描述

给定一个字符串,求字符串中字典序最大的子序列.字典序最大的子序列是这样构造的:给定一个字符串 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