高效的算法perl或python

Question

面试官问了一个问题要写得快& &;以下函数的有效算法，

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

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

string只能由'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' string

ABCAAB -> AACAAB [AB = AA]
[au:] [au:]
[au:] [au:]
AAAAB -> AAAB [AA = A]
AAAB -> AAAB [AA = A]
[au:] [au:]
AB -> AA [AB = AA]
AA -> A [AA = A]

最终结果:'A'
因为我们现在不能对字符串应用更多的规则。

My Answer is like(伪代码):

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

Answer 3

这是一个python解决方案:

In [34]: import ranodm
In [35]: rules = {"AB":"AA",'AC':'AA','AA':'A','CC':'C','BC':'BB','BB':'B'}
In [36]: keys = rules.keys()
In [37]: keys
Out[37]: ['AA', 'AC', 'AB', 'BB', 'BC', 'CC']
In [38]: mystr = 'ABCAAB' 
In [42]: while len(mystr)>=2:
    r = random.choice(keys) #choose one rule randomly 
    mystr = mystr.replace(r,rules[r])
   ....:   
In [43]: mystr
Out[43]: 'A'

Answer 4

Yves Daoust的答案是正确的，模拟它没有意义。这似乎是一个狡猾的问题，你应该意识到这一点，理解这种行为，并直接实现它。

Yves的方法是有效的，但这里有一个类似的实际实现:

def transform(string):
    a = string.find('A') + 1
    b = string.find('B', 0, a or len(string)) + 1
    return 'C' * string.startswith('C') + 'B' * (b>0) + 'A' * (a>0)

我搜索第一个'A'，然后搜索它左边的'B'(或者在整个字符串中，如果没有'A')。它告诉我B和A是否属于输出。对于'C'，我只需要检查字符串的开始。虽然我可能扫描整个字符串两次，而不是像Yves建议的那样只扫描一次，使用find函数使它非常快，大约比"手工"循环字符串快100倍，只是寻找一个"a"(这只是在我的测试字符串的末尾):

>>> from timeit import timeit
>>> s = 'C' * 100000000 + 'BA'
>>> timeit(lambda: transform(s), number=1)
0.10583857561359977
>>> timeit(lambda: next(x for x in s if x == 'A'), number=1)
10.957446603791382

您可以通过使用lstrip('C')来查找第一个非'C'字符，这比手动操作要快，但这会使用额外的内存，并且仍然比find慢得多:

>>> timeit(lambda: s.lstrip('C'), number=1)
2.411250071361735

正则表达式可能也可以做到这一点，但即使只是扫描我的teststring一次，只是寻找'A'需要的时间比我的整个transform:

>>> timeit(lambda: re.search('A', s), number=1)
0.13403880409939006