string - Perl Morgan 和字符串？

Question

我正在尝试解决 this hackerrank 上的问题:

所以问题是:

jack 和丹尼尔是 friend 。他们都喜欢字母，尤其是大写字母。他们正在从报纸上剪下大写字母，每个人都将自己收集的字母分开存放。一个美好的一天，摩根拜访了 jack 和丹尼尔。他看到了他们的收藏品。 Morgan 想知道由这两个集合组成的字典序最小的字符串是什么。当它位于堆栈顶部时，他可以从集合中取出一封信。还有，Morgan 想用男孩收藏中的所有字母。

这是我在 Perl 中的尝试:

#!/usr/bin/perl
use strict;
use warnings;
chomp(my $n=<>);
while($n>0){
    chomp(my $string1=<>);
    chomp(my $string2=<>);
    lexi($string1,$string2);
    $n--;
}
sub lexi{
   my($str1,$str2)=@_;
   my @str1=split(//,$str1);
   my @str2=split(//,$str2);
   my $final_string="";

   while(@str2 && @str1){
       my $st2=$str2[0];
       my $st1=$str1[0];
       if($st1 le $st2){
         $final_string.=$st1;
         shift @str1;
       }
       else{
          $final_string.=$st2;
          shift @str2;
       }
  }
  if(@str1){
       $final_string=$final_string.join('',@str1);
  }
  else{
       $final_string=$final_string.join('',@str2);
  }
  print $final_string,"\n";
}

示例输入:

2
JACK
DANIEL
ABACABA
ABACABA

第一行包含测试用例的数量 T。接下来的每两行都是这样的格式:第一行包含字符串A，第二行包含字符串B。

示例输出:

DAJACKNIEL
AABABACABACABA

但是对于示例测试用例，它给出了正确的结果，而对于其他测试用例给出了错误的结果/em>。它给出错误结果的一种情况是

1
AABAC
AACAB

它输出 AAAABACCAB 而不是 AAAABACABC。

我不知道该算法有什么问题以及为什么其他测试用例会失败？

更新:

根据@squeamishossifrage 评论 如果我添加

($str1,$str2)=sort{$a cmp $b}($str1,$str2);

无论用户输入如何，结果都一样，但测试用例仍然失败。

Answer 1

问题在于您对相等字符的处理。举个例子:

ACBA
BCAB

当面对两个相同的字符(在我的示例中为 C)时，您天真地从第一个字符串中选择了一个，但这并不总是正确的。你需要向前看才能打破僵局。您甚至可能需要提前查看许多字符。在这种情况下，第二个字符串的 C 之后的下一个字符低于第一个字符串的下一个字符，因此您应该先从第二个字符串中取出 C。

通过将字符串保留为字符串，简单的字符串比较将根据需要比较尽可能多的字符以确定要使用的字符。

sub lexi {
   my ($str1, $str2) = @_;

   utf8::downgrade($str1);  # Makes sure length() will be fast
   utf8::downgrade($str2);  # since we only have ASCII letters.

   my $final_string = "";
   while (length($str2) && length($str1)) {
      $final_string .= substr($str1 le $str2 ? $str1 : $str2, 0, 1, '');
   }

   $final_string .= $str1;
   $final_string .= $str2;
   print $final_string, "\n";
}