给定一个字符串S和一个整数K,我们必须找到一个字符串T,如果我们对字符串S的所有子序列进行字典序排序,那么T位于第k个位置。
以下是problem Link的链接
我在练习动态编程的问题时遇到了这个问题。然而,我没能解决这个问题。
发布于 2016-12-23 16:09:33
好吧,我不能给你精确的算法,因为我看到链接的描述与你的不同。但您可以使用深度优先搜索的变体来完成此任务。
1)做一个算法,在控制台上打印所有正常的子串。使用深度拳头搜索算法遍历字符。算法的每一次迭代都应该产生一个单词。考虑到您通过了一个带有循环的图,因此您将需要在每次迭代中存储所有已经传递的字符-使用容器。
2)创建一个函数,该函数考虑到当前深度级别的已处理字符,返回下一个词典字符的索引。修改您的算法,使其返回具有特定长度的字典序字符串。
请注意,此函数需要从您的链接添加问题。有一个要求必须保持字符的顺序。因此,在将“已处理字符”传递到下一次迭代之前,您还需要使当前字符左侧的所有字符都被处理。
4)代替打印子字符串,现在将它们存储在一个容器中,并为每个子字符串增加一个计数器。如果您已经处理了相同的单词,则不会增加计数器。当你的计数器达到T时,你就会信守诺言。如果算法完成并且计数器不等于T,则打印"Eel“。
https://stackoverflow.com/questions/41287994
复制