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

例如，下面的情况需要"forever"来获得结果:

00111010000001000111010000101111110101110001001 AAAAAAAAAAAAAAABBBBBAAABBAAAAAAAAAAAAAAAAAAAAAAAAAAAABAAAAAAAAAAAABBBBBBAAAAAAAAAAAAAAAAAAAAAABBBBAAAAAAAAAABBBBBBBBBBBBBAAAAAAAAAAABBBBBBAAAABBAAAAAAAAAAAAAAA

等待检测的病例甚至更长。

下面是我的代码:

#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. 假设我的代码是正确的，很明显，递归不是最好的解决方案(太多回溯)，我有一种感觉，通过使用DP来解决它。我试过记忆来存储(I, j)的结果，但仍然失败了。需要想法来解决这个问题。

感谢您的时间和评论!

Answer 1

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

假设State[i,j]用于保存模式[i]和文本[j]的状态，如果State[i,j] == true，我们说从模式[0]到模式[i]，从文本[0]到文本[j]，序列转换是有效的。因此，我们可以根据以下条件计算状态[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 

感谢您的时间和评论!