algorithm - CodeEval 序列变换算法

Question

挑战说明:

有两个序列。第一个序列由数字“0”和“1”组成，第二个序列由字母“A”和“B”组成。挑战在于确定是否可以使用以下规则将给定的二进制序列转换为字符串序列:
1、“0”可以转化为非空字母序列“A”(“A”、“AA”、“AAA”等)
2、“1”可以转化为非空字母序列“A”(“A”、“AA”、“AAA”等)或非空字母序列“B”(“B”、“BB” , "BBB"等)例如

还有一些输入:
1010 AAAAABBBBAAAA - 有效
00 AAAAAA - 有效
01001110 AAAABAAABBBBBBAAAAAAA - 有效
1100110 BBAABABBA - 无效


我想知道算法应该是什么样子？

附言一点头绪都没有

Answer 1

经过几天尝试各种解决方案，我终于解决了这个问题。我不会为您提供答案，但这是方法。

以这个测试用例为例:

1010 AAAAABBBBAAAA

注意1010可以用正则表达式代替

(A+|B+)A+(A+|B+)A+

这个正则表达式可以生成无限数量的字符串，对一个字符串进行这种分析的最坏情况时间复杂度是指数级的

但字符串“AAAAABBBBAAAA”只能由有限数量的由 (A+) 和 (A+|B+) 组成的正则表达式来描述，或者在本例中为 0 和 1