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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * longest common subsequence
 * @param s1 string字符串 the string
 * @param s2 string字符串 the string
 * @return string字符串
 */

#define max(a,b) a>b?a:b

char* LCS(char* s1, char* s2 ) {
    // write code here
    int row = strlen(s2) + 1;
    int col = strlen(s1) + 1;

    int len_calculator[row][col];
    int i = 0;
    for(; i < col; i++) {
        len_calculator[0][i] = 0;
    }
    int j;
    for(i = 1; i < row; i++) {
        j = 0;
        len_calculator[i][j] = 0;
        for(j = 1; j < col; j++) {
            if(s2[i - 1] == s1[j - 1]) {
                len_calculator[i][j] = len_calculator[i - 1][j - 1] + 1;
            } else {
                len_calculator[i][j] = max(len_calculator[i - 1][j], len_calculator[i][j - 1]);
            }
        }
    }

    char *ret = (char*)malloc(len_calculator[row - 1][col - 1] + 1);
    if(len_calculator[row - 1][col - 1] == 0) {
        return "-1";
    }
    ret[len_calculator[row - 1][col - 1]] = '\0';
    i = row - 1;
    j = col - 1;
    int index = len_calculator[i][j] - 1;
    while(i > 0 && j > 0) {
        if(len_calculator[i][j] == len_calculator[i - 1][j]) {
            i--;
        } else if(len_calculator[i][j] == len_calculator[i][j - 1]) {
            j--;
        } else {
            ret[index--] = s2[i - 1];
            i--;
            j--;
        }
    }
    return ret;
}