高效算法：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条规则随机应用于给定字符串中的每一条，并将最终转换后的字符串作为输出

例如，函数的输入为：'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

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

- Murtuza Z

---

你有什么问题或困惑吗？ - Karoly Horvath

@Karoly：请为上述问题提出优化的解决方案/算法。 - Murtuza Z

@Rob：我写了一个循环，因为他们告诉我一次只能应用一条规则，所以我们不能在模式匹配中使用全局标识符“g”。:( - Murtuza Z

我猜有一个诀窍：替换的顺序并不重要。 - user1196549

如果代码完全正常工作，最好在CodeReview.SE上进行。 - Izkata

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。

- user1196549

---

谢谢您让它变得如此简单。 - Murtuza Z

不客气。看到长度达到了20亿的提示，我就知道其中有诀窍。 - user1196549

你有好的想法如何实际实现它吗？在我的回答中，我使用 find（），因为它非常快。但是我需要两次扫描。我想不到只扫描一次的更快的方法。 - Stefan Pochmann

三个if测试和三个while循环。除了病态情况，速度在这里不是问题，解析会在第一个A处停止。 - user1196549

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

- mpapec

---

@n33rma，没有/g开关。 - mpapec

让我试试，非常感谢您的解决方案。 - Murtuza Z

抱歉，我无法投票给你的答案，它显示“您需要15个声望才能投票”。 - Murtuza Z

@n33rma：现在你可以投票了。你已经有足够的声望来点赞了 :) - serenesat

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'

- Moj

---

非常感谢您的解决方案。 - Murtuza Z

是的，我尝试了，但它说“您需要15个声望才能投票”。对此很抱歉。 - Murtuza Z

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'，然后在它左边（或整个字符串中，如果没有'A'）查找'B'。这告诉我'B'和'A'是否属于输出。对于'C'，我只需要检查字符串的开头。虽然我可能会扫描整个字符串两次而不是像Yves建议的那样只扫描一次，但使用find函数使其非常快，比手动循环遍历字符串并查找'A'（仅在我的测试字符串末尾）快大约100倍：

>>> 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

正则表达式可能也可以做到，但是即使只是扫描我的测试字符串一次来查找“A”，所花费的时间也比我整个transform函数的执行时间还要长：

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

- Stefan Pochmann