python - 高效算法perl或python

Question

面试官在面试中问了一个问题，为以下功能编写快速高效的算法，

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

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

string should be made from only 'A','B' & 'C' characters like 'AAA' ,'ABCABC','AAAABBBBABAAACCCA'

转换规则:

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

每次对给定的字符串随机应用以上 6 条规则，并将最终转换后的字符串作为输出

例如函数的输入是:'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。

明确应用规则和多次通过的解决方案是 Not Acceptable ，因为它们的行为可以是 O(N²) 甚至 O(N³)，而 N =2000000000.