合并两个字符串并生成词典中最小的合并字符串。
合并两个字符串并生成词典中最小的合并字符串。
提问于 2016-06-15 17:07:57
当我遇到一个相当简单的子问题时，我正在解决一个问题。给定两个字符串S1和S2，merge(S1,S2)表示通过穿插两个字符串( S1和S2 )获得的任何字符串，在这两个字符串中都保持字符的顺序，这样得到的字符串在字典上是最小的。
示例
S1 = abad
S2 = bbde
merge(S1, S2) = ababbdde现在，我试图通过应用一种贪婪的技术来解决这个问题，从字符串的第一个元素开始，然后查找最小的元素并将其添加到结果中。但是，很快我发现这并不总是导致最优解。代码如下所示。
int n = a.size(), m = b.size();
int i =0, j=0, k=0; char array[n+m];
for(; i< n && j<n;) {
if(a[i] < b[j]) {
array[k] = a[i];
++i;
}
else {
array[k] = b[j];
++j;
}
++k;
}
while(i<n) {
array[k] = a[i];
++i;
++k;
}
while(j<m) {
array[k] = b[j];
++j;
++k;
}
for (int i = 0; i < n+m; ++i) {
cout<<array[i];
}
cout<<endl;我想要向后遍历并选择最大的字符，然后开始从后面添加。通过有限的测试，我完成了这个任务，看上去不错。
int n = a.size(), m = b.size();
int i =n-1, j=m-1, k=n+m-1; char array[n+m];
for(; i>=0 && j>=0;) {
if(a[i] > b[j]) {
array[k] = a[i];
--i;
}
else {
array[k] = b[j];
--j;
}
--k;
}
while(i>=0) {
array[k] = a[i];
--i;
--k;
}
while(j>=0) {
array[k] = b[j];
--j;
--k;
}
for (int i = 0; i < n + m; ++i) {
cout<<array[i];
}
cout<<endl;但是，我不确定这是否总是给出最优解。
这个解一开始是正确的吗?如果是的话，有人能给我一个小小的证据来说明为什么这总是产生最优解。
回答 4
Stack Overflow用户
发布于 2021-02-07 16:31:45
然而，贪婪的方法起作用了，
if(a[i] < b[j]) {
array[k] = a[i];
++i;
}
else {
array[k] = b[j];
++j;
}这个部分是不正确的，因为当a[i] == b[j]不能简单地将b[j]分配给array[k]。
相反，您需要比较子字符串a[i:]和b[j:]在a[i] == b[j]时的情况，您只需对std::string本身进行操作：
if(s1[i] < s2[j])
{
array[k] = s1[i];
++i;
}
else if (s1[i] == s2[j] && s1.substr(i) < s2.substr(j))
{
array[k] = s1[i];
++i;
}
else
{
array[k] = s2[j];
++j;
}时间复杂度将是二次(O(n^2))，因为substr操作需要O(n)。
Stack Overflow用户
发布于 2016-06-15 18:55:05
下面是基于我之前的评论的完整解决方案。
import string
import random
global brute_force_lowest
global almost_greedy_lowest
global brute_force_calls
global almost_greedy_calls
def brute_force(p, a, b):
global brute_force_lowest
global brute_force_calls
brute_force_calls += 1
if len(a) > 0: brute_force(p + a[0], a[1:], b)
if len(b) > 0: brute_force(p + b[0], a, b[1:])
if len(a) == 0 and len(b) == 0:
if p < brute_force_lowest: brute_force_lowest = p
def almost_greedy(p, a, b):
global almost_greedy_lowest
global almost_greedy_calls
almost_greedy_calls += 1
if len(a) == 0 and len(b) == 0:
if p < almost_greedy_lowest: almost_greedy_lowest = p
elif len(b) == 0:
almost_greedy(p + a, '', '')
elif len(a) == 0:
almost_greedy(p + b, '', '')
elif a[0] < b[0]:
almost_greedy(p + a[0], a[1:], b)
elif a[0] > b[0]:
almost_greedy(p + b[0], a, b[1:])
else:
almost_greedy(p + a[0], a[1:], b)
almost_greedy(p + b[0], a, b[1:])
for j in range(10000):
a = ''.join(random.choice(string.ascii_lowercase) for _ in range(random.randint(2, 10)))
b = ''.join(random.choice(string.ascii_lowercase) for _ in range(random.randint(2, 10)))
brute_force_lowest = a + b
brute_force_calls = 0
brute_force('', a, b)
almost_greedy_calls = 0
almost_greedy_lowest = a + b
almost_greedy('', a, b)
print('%s, %s -> %s vs. %s (%.3f)' % (a, b, brute_force_lowest, almost_greedy_lowest, float(almost_greedy_calls) / brute_force_calls))
if almost_greedy_lowest != brute_force_lowest: print 'ERROR'
一个有趣的统计数据是，如果我们把字母表限制在'ab‘的话，这个算法的工作速度大约是蛮力算法的10倍。
更新一些优化：
def prefix_length(a):
for i in range(len(a)):
if a[i] != a[0]: return i
return len(a)
def almost_greedy(p, a, b):
global almost_greedy_lowest
global almost_greedy_calls
almost_greedy_calls += 1
if p > almost_greedy_lowest: return
if len(a) == 0 and len(b) == 0:
if p < almost_greedy_lowest: almost_greedy_lowest = p
elif len(b) == 0:
almost_greedy(p + a, '', '')
elif len(a) == 0:
almost_greedy(p + b, '', '')
elif a[0] < b[0]:
almost_greedy(p + a[0], a[1:], b)
elif a[0] > b[0]:
almost_greedy(p + b[0], a, b[1:])
else:
la = prefix_length(a)
almost_greedy(p + a[0] * la, a[la:], b)
lb = prefix_length(b)
almost_greedy(p + b[0] * lb, a, b[lb:])Stack Overflow用户
发布于 2016-06-15 18:27:50
贪婪会解决问题。要解决这个问题，您必须确定地访问两个字符串。
在您的代码中，您丢失了一个地方，即您的第一个for循环if(a[i] < b[j])，它应该是if(a[i] <= b[j])。检查代码这里
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/37841656
复制相关文章
相似问题
腾讯云开发者
