用于查找满足给定顺序的唯一字符的字典式最小字符串的算法

Question

如何找到字典中最小的字符串，并且具有满足以填充'>'的字符串形式给出的顺序的唯一字符和'<'。例如，对字符串'<lt<lt；'是"abcde"，因为"a<b<c<d<e.怎么做？

Answer 1

对于字符串长度N，制作一个具有N+1个节点和N条有向边的图，其中p[i] < p[j]表示从第i个节点到第j个节点的边。

然后对这个图进行拓扑排序。

使违反自然顺序且它们之间没有边的最小结果交换邻居对(见Uniqueness节(

将字母字符按排序顺序分配给节点

1<2<3>4
graph:
1 -> 2 -> 3
^
/  
4

1 4 2 3  //one of the possible topologic orderings
1 2 4 3  //after 2/4 swap 
| | | |  
a b c d  //assign letters
a<b<d>c 

Answer 2

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

我会扩展输入字符串，这样它就会得到一个额外的"<quot；在它的末端。

我们现在可以进行一些观察：如果我们找到一个"<quot；在输入字符串中的位置k，则我们应该输出拉丁字母表中的第k+sup>个字母。

然而，如果我们发现一个">quot；在位置k处>"；，直到下一个"<"；。总有一个"<quot；下面，因为我们在末尾添加了一个额外的。让下一个"<quot；位于m的位置。

对于那些m-k的位置，我们现在首先从拉丁字母表中产生m^th字母，然后产生(m-1(^th。。。直到字母表的第k^个字母。

以下是伪代码的实现：

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

Answer 3

问题是用从0到n-1的数字填充数组，这样可以尊重局部不等式，并尽可能将最低的数字定位在数组的开头。

一个简单的解决方案是以相反的顺序读取输入字符串，首先尝试放置n-1，然后放置n-2等。

当遇到<时，将当前值写入堆栈中。如果没有，则读取堆栈。

输出：

>>    -> cba
<<<<  -> abcde
<<><  -> abdce
>>>>  -> edcba
><>>  -> baedc

C++中的代码：

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
#include <numeric>
std::string smallest_s (const std::string &s_in) {
int n = s_in.size() + 1;
std::string s;
s.resize(n);
std::vector<int> ans (n);
int index = n-1;
std::stack<int> qu;
qu.push (n-1);
for (int j = n-2; j >= 0; j--) {
if (s_in[j] == '<') {
while (!qu.empty()) {
ans[index--] = qu.top();
qu.pop();
}
} 
qu.push (j);
}
while (!qu.empty()) {
ans[index--] = qu.top();
qu.pop();
}
for (int i = 0; i < n; ++i)
s[i] = 'a' + ans[i];
return s;
}

int main() {

for (const std::string &s_in: {">>", "<<<<", "<<><", ">>>>", "><>>"}) {
std::cout << s_in << " -> " << smallest_s(s_in) << 'n';
}
}