关于判断字符串是否能够合并的问题

Question

求问这个问题如何用c语言编程解决！因为递归方法时间复杂度太高，请用动态规划方法，谢谢！

Answer 1

#include <stdio.h>

int canconcat(char *s1, char *s2, char * s3)
{
    int r1 = 0, r2 = 0;
    if (*s3 == 0 && (*s1 || *s2)) return 0;
    if (*s1 == 0 && *s2 == 0) return 1;
    if (*s1 != 0 && *s1 == *s3)
    {
        r1 = canconcat(s1 + 1, s2, s3 + 1);
    }
    if (*s2 != 0 && *s2 == *s3)
    {
        r2 = canconcat(s1, s2 + 1, s3 + 1);
    }
    if (*s1 == 0 && *s2 != 0)
        return r2;
    if (*s1 != 0 && *s2 == 0)
        return r1;
    return r1 || r2;
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        char s1[201], s2[201], s3[402];
        scanf("%s%s%s", s1, s2, s3);
        if (canconcat(s1, s2, s3))
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}