高效的perl或python算法

Question

面试官在一次采访中问了一个问题,为下面的功能编写快速有效的算法,

问题:编写一个函数来解析给定字符串以下给定的规则并生成最终解析的字符串作为输出

写一个接受字符串作为输入的函数,字符串长度将在[0..2000000000]之间

字符串应仅由'A','B'和'C'字符组成,如'AAA','ABCABC','AAAABBBBABAAACCCA'

转型规则:

1)'AB' - >'AA'2
)'AC' - >'AA'3
)'AA' - >'
A'4)'CC' - >'C'5
)'BC' - >'BB'
6)'BB' - >'B'

每次在给定字符串上随机应用所有6个以上规则,并将最终转换后的字符串作为输出

例如,对Function的输入是:'ABCAAB'字符串

ABCAAB - > AACAAB [AB = AA]
AACAAB - > ACAAB [AA = A]
ACAAB - > AAAAB [AC = AA]
AAAAB - > AAAB [AA = A]
AAAB - > AAB [AA = A]
AAB - > AB [ AA = A]
AB - > AA [AB = AA]
AA - > A [AA = A]

最终结果:'A'
因为我们现在无法对字符串应用任何其他规则.

我的答案就像(伪代码):

sub myFunc {
my $str = @_;
flag = 1
while(flag ==1) {
    if ($str =~ /AB/){
    $str =~ s/AB/AA/;
    next;
    }
    elsif($str =~ /AC/){
    $str =~ s/AC/AA/;
    next;
    }
    elsif($str =~ /AA/){
    $str =~ s/AA/A/;
    next;
    }
    elsif($str =~ /CC/){ 
    $str =~ s/CC/C/;
    next;
    }
    elsif($str =~ /BC/){ 
    $str =~ s/BC/BB/;
    next;
    }
    elsif($str =~ /BB/){ 
    $str =~ s/BB/B/;
    next;
    }
    else
    {
        flag = 0
    }
} //while
 return $str;
} //func

有人可以为上述问题提出更好的算法和方法吗？

Answer 1

规则1至3将丢弃A之后的任何字符.
规则5和6将丢弃B之后的任何B和C.
规则4将丢弃C之后的任何C.替换的顺序无关紧要.

因此在处理之后,字符串将是C,CB,CA,CBA,B,BA,A之一.

单次扫描字符串就足够了.如果你看到C,请保留它并跳过下一个C; 然后,如果你看到B,保留它并跳过下一个B; 然后,如果你看到一个A保持它并停止.

给定的例子ABCAAB立即产生A.

明确应用规则和多次通过的解决方案是不可接受的,因为他们的行为可以是O(N²)甚至是O(N³),同时N=2000000000.

Answer 2

您可以在匹配转换规则时重复替换,

my %h = (
  'AB' => 'AA',
  'AC' => 'AA', 
  'AA' => 'A', 
  'CC' => 'C', 
  'BC' => 'BB', 
  'BB' => 'B', 
);
my $s = 'ABCAAB';

1 while $s =~ s/(AB|AC|AA|CC|BC|BB)/$h{$1}/; # also without /g switch
print $s;

产量

A