【代码随想录-动态规划】最长公共子序列

T1143、最长公共子序列

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

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

这个题目变种可以变成522. 最长特殊序列 II

判断一个字符串 s 是否是另一个字符串 t 的子序列

就是当最长公共子序列 == s.length() 时，$$s\in t$$

思路
step1、dp[i][j] 表示 text1[0:i-1] 和 text2[0:j-1] 的最长子序列长度是 dp[i][j]
step2、

当text1[i-1] == text2[j-1]时

dp[i][j] = dp[i-1][j-1] + 1

当text1[i-1] != text2[j-1]时

dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    private boolean check(String a, String b){
    
        // 判断a 是否 是 b的子序列
        // a 是源串 b是可改变串
        int l1 = a.length();
        int l2 = b.length();
        if(l1 > l2) return false;
        int[][] dp = new int[l1+1][l2+1];
        for(int i = 1; i <= l1; i++){
    
            for(int j = 1; j <= l2; j++){
    
                if(a.charAt(i-1) == b.charAt(j-1)){
    
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
    
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        if(dp[l1][l2] == l1) return true;
        return false;
    }

T522. 最长特殊序列 II

 public int findLUSlength(String[] strs) {
    
        int n = strs.length;
        // 判断一个串是否是其他的子串
        int ret = -1;
        for (int i = 0; i < n; i++) {
    
            if (strs[i].length() <= ret) continue;
            boolean ok = true;
            for (int j = 0; j < n && ok; j++) {
    
                if (i == j) continue;
                if (check(strs[i], strs[j])) ok = false;
            }
            if (ok) ret = strs[i].length();
        }
        return ret;
    }