题解 | #最长公共子序列(二)#

/**
 * longest common subsequence
 * @param s1 string字符串 the string
 * @param s2 string字符串 the string
 * @return string字符串
 */
int max(int a,int b)
{
    return a>b?a:b;
}
char* LCS(char* s1, char* s2 ) {
    // write code here
    int len1=strlen(s1);
    int len2=strlen(s2);
    int dp[len1+1][len2+1];
    if(len1==0||len2==0)
    {
        return "-1";
    }
    for(int i=0;i<len1+1;i++)
    {
        dp[i][0]=0;
    }
    for(int j=0;j<len2+1;j++)
    {
        dp[0][j]=0;
    }

    int i,j;
    for(i=1;i<len1+1;i++)
    {
        for(j=1;j<len2+1;j++)
        {
            if(s1[i-1]==s2[j-1])
            {
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }

    int LCS=dp[len1][len2];
    if(LCS==0)
    {
        return "-1";
    }
    char *ret=(char*)malloc(sizeof(char)*LCS+1);
    ret[LCS--]='\0';
    i--;
    j--;
    while (i!=0&&j!=0)
    {
        if(dp[i][j]>dp[i-1][j]&&dp[i][j]>dp[i][j-1])
        {
            ret[LCS--]=s1[i-1];
            i--;
            j--;
        }
        else if(dp[i][j]==dp[i][j-1]&&dp[i][j]>dp[i-1][j])
        {
            j--;
        }
        else if(dp[i][j]==dp[i-1][j]&&dp[i][j]>dp[i][j-1])
        {
            i--;
        }
        else
        {
            i--;
            j--;
        }
    }
    return ret;
}