algorithm - CodeEval/序列转换代码超时

Question

挑战描述在这里:https://www.codeeval.com/browse/130/

两条规则:

1. “0”可以转化为非空字母序列“A”(“A”、“AA”、“AAA”等)
2. “1”可以转换为非空字母序列“A”(“A”、“AA”、“AAA”等)或非空字母序列“B”(“B”、“BB” ”、“BBB”等)例如

测试用例:

1. 1010 AAAAABBBBAAAA ==> 是
2. 00 AAAAAA ==> 是
3. 01001110 AAAABAAABBBBBBAAAAAAA ==> 是
4. 1100110 BBAABABBA ==> 否

我想到的解决方案是正则表达式，我递归地实现了。对于上面的小测试用例，它工作正常。但是当涉及到长字符串时，代码运行超时超过 10 秒。

例如，下面的情况需要“永远”才能得到结果:

00111010000001000111010000101111110101110001001

还有更长的案例等待测试。

这是我的代码:

#include <iostream>
using namespace std;

bool validate(string pattern, int i, string text, int j);

bool matchA(string pattern, int i, string text, int j)
{
    while(j < text.size() && text[j] == 'A')
    {
        j++;
        if(validate(pattern, i+1, text, j))
            return true;
    }
    return false;
}

bool matchAB(string pattern, int i, string text, int j, char c)
{
    while(j < text.size() && text[j] == c)
    {
        j++;
        if(validate(pattern, i+1, text, j))
            return true;
    }
    return false;
}

bool validate(string pattern, int i, string text, int j)
{
    if(i == pattern.size())
        return j == text.size();
    if(pattern[i] == '0')
        return matchA(pattern, i, text, j);
    if(pattern[i] == '1')
        return matchAB(pattern, i, text, j, text[j]);
    return false;
}

int main(int argc, char* argv[])
{
    string pattern = "00";
    string text = "AAAAA";
    if(validate(pattern, 0, text, 0))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

我的问题是:

1. 如何证明上面代码的正确性(具有讽刺意味的是，我对我写的递归不是很有信心)？
2. 如果代码不对，如何调试？
3. 假设我的代码是正确的，很明显递归不是最好的解决方案(回溯太多)，我有一种使用DP来解决它的感觉。我试过内存来存储 (i, j) 的结果，但还是失败了。需要解决这个问题的想法。

感谢您的宝贵时间和意见!

Answer 1

感谢@jonderry 的提示，DP 解决方案如下:

假设State[i,j]用来保存pattern[i]和text[j]的状态，如果State[i,j] == true，我们说从pattern[0]到pattern[i] ]，从text[0]到text[j]，序列变换是有效的。因此，我们可以根据以下条件计算State[i,j]:

State[i,j] =
1. (pattern[i] == '0' and text[j] == 'A') or pattern[i] == '1'   // if State[i-1,j-1] = true
2. State[i-1,j] && text[j-1] == text[j],                         // otherwise 

感谢您的宝贵时间和意见!