查找在字典上满足给定顺序的唯一字符的最小字符串的算法 [英] Algorithm for finding the lexicographically smallest string of unique characters satisfying given order

问题描述

如何查找按字典顺序排列的最小字符串，并具有满足以'>'填充的字符串形式给出的顺序的独特字符和'<'.例如，回答字符串'<<<<'是'abcde'是因为'a< b< c< d< e.如何进行?

How to find the lexicographically smallest string and has unique characters that satisfies the order given in the form of a string filled with '>' and '<'.For example, answer for the string '<<<<' is 'abcde' because 'a<b<c<d<e.How to go about it?

推荐答案

如果我正确理解，您的输入字符串将比预期的输出字符串少一个字符，因为每个字符都描述了两个连续字符之间的关系.而且似乎您也希望输出仅包含小写拉丁字母.

If I understand correctly your input string would have one character less than the expected output string, since each character describes a relationship between two consecutive characters. And it also seems you want the output to consist of lowercase Latin letters only.

我会扩展该输入字符串，因此会得到一个额外的<".在其末尾.

I would extend that input string, so it gets an extra "<" at its end.

我们现在可以进行一些观察:如果找到<"在输入字符串中 k 的位置，那么我们应该从拉丁字母输出 k ^th 字母.

We can make some observations now: if we find a "<" at position k in the input string, then we should output the k^th letter from the Latin alphabet.

但是，如果我们找到一个>"在位置 k 处，我们应该寻找这一系列>"的结尾，直到下一个<".总是有一个<"接下来，因为我们在末尾添加了一个额外的内容.令下一个<"的位置为0.在 m 位置.

If however we find a ">" at position k, we should look for the end of this series of ">", up to the next "<". There is always a "<" following, since we added an extra one at the end. Let the position of the next "<" be at position m.

对于那些 mk 职位，我们现在首先从拉丁字母生成 m ^th 字母，然后生成(m-1) ^th 等，直到字母的 k ^th 字母.

For those m-k positions we now produce the m^th letter from the Latin alphabet first, then the (m-1)^th, ...etc, down to the k^th letter of the alphabet.

这是伪代码的实现:

solve(str):
    letters := "abcdefghijklmnopqrstuvwxyz"
    str.append("<")
    output := ""
    i := 0    
    while i < len(str) do
        if str[i] is "<" then
            output.append(letters[i])
        else
            start := i
            while str[i] is ">" do
                i := i + 1
            j := i
            while j >= start do
                output.append(letters[j])
                j := j - 1
        i := i + 1
    return output

这篇关于查找在字典上满足给定顺序的唯一字符的最小字符串的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！