[97] Interleaving String

哇～用手寫畫了個metric 終於想懂之後

又龜速的寫一點寫一點

最後沒有debug 太多次就pass了

我的眼淚都要流下來了

那就這樣以示慶祝 XD（花惹發XD）

前一輪刷題的時候寫這個是以放棄作結啊～我真是太感動了

bool isInterleave(char * s1, char * s2, char * s3){

int l1=strlen(s1);

int l2=strlen(s2);

int l3=strlen(s3);

if (l3 != (l1+l2))

return false;

if (l1==0)

return !strcmp(s2,s3);

if (l2==0)

return !strcmp(s1,s3);

bool **dp = malloc (sizeof (bool*)* (l1+1));

for (int i=0;i<=l1;i++)

dp[i]=malloc (sizeof(bool)*(l2+1));

dp[0][0]=true;

for (int i=1;i <=l1;i++)

{

if ((s1[i-1]==s3[i-1]) && dp[i-1][0]== true)

dp[i][0]= true;

else

dp[i][0]= false;

}

for (int j=1;j <=l2;j++)

{

if ((s2[j-1]==s3[j-1]) && dp[0][j-1] == true)

dp[0][j]=true;

else

dp[0][j]=false;

}

//printf(" %d %d %d\n", l1,l2,l3);

for (int i=1;i<=l1;i++)

for (int j=1;j<=l2;j++)

{

if ((dp[i-1][j]== true) && (s3[i+j-1]==s1[i-1]))

dp[i][j]=true;

else if ((dp[i][j-1]==true) && (s3[i+j-1]==s2[j-1]))

dp[i][j]=true;

else

dp[i][j]=false;

}

return dp[l1][l2];

}