最长公共子序列(Longest Common Subsequence)

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例 1:

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace"，它的长度为 3。

示例 2:

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。

示例 3:

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。

提示:

  • 1 <= text1.length <= 1000
  • 1 <= text2.length <= 1000
  • 输入的字符串只含有小写英文字符。
int lcs(char* text1, char* text2, int m, int n) {
    if(m == 0||n == 0) return 0;
    if(text1[m-1] == text2[n-1]) {
        return lcs(text1,text2,m-1,n-1)+1;
    }else {
        int discard1 = lcs(text1, text2, m-1, n);
        int discard2 = lcs(text1, text2, m, n-1);
        if(discard1 > discard2){
            return discard1;
        }else {
            return discard2;
        }
    }
}
int longestCommonSubsequence(char* text1, char* text2){
    int len1 = strlen(text1);
    int len2 = strlen(text2);
    return lcs(text1, text2, len1, len2);
}

但是这种方法显然会爆炸，递归太多，超时

int lcs(char* text1, char* text2, int m, int n, int** cache) {
    if(m == 0||n == 0) return 0;
    int result = 0;
    if(cache[m][n] != -1)
        return cache[m][n];
    if(text1[m-1] == text2[n-1]) {
        result = lcs(text1,text2,m-1,n-1,cache)+1;
    }else {
        int discard1 = lcs(text1, text2, m-1, n,cache);
        int discard2 = lcs(text1, text2, m, n-1,cache);
        if(discard1 > discard2){
            result = discard1;
        }else {
            result = discard2;
        }
    }
    cache[m][n] = result;
    return result;
}
int longestCommonSubsequence(char* text1, char* text2){
    
    int len1 = strlen(text1);
    int len2 = strlen(text2);
    int** cache = malloc((len1+1)*sizeof(int*));
    for(int i =0;i<=len1;i++){
        cache[i] = malloc((len2+1)*sizeof(int));
    }
    for(int i =0;i<=len1;i++){
        for(int j = 0;j<=len2;j++){
            cache[i][j]=-1;
        }
    }

    int length = lcs(text1, text2, len1, len2, cache);

    for(int i =0;i<=len1;i++){
        free(cache[i]);
    }
    free(cache);
    return length;
}

这种方法就ok了，经典空间换时间