[code Capriccio - dynamic planning] longest common subsequence

T1143、 Longest common subsequence

Given two strings text1 and text2, Returns the length of the longest common subsequence of these two strings .
A string of Subsequence This is a new string ： It is to delete some characters from the original string without changing the relative order of the characters （ You can also delete no characters ） After the composition of the new string .
for example ,“ace” yes “abcde” The subsequence , but “aec” No “abcde” The subsequence . Two strings of 「 Common subsequence 」 Is the subsequence shared by these two strings .
If the two strings have no common subsequence , Then return to 0.

Given two strings text1 and text2, Returns the length of the longest common subsequence of these two strings

The variant of this topic can become 522. The longest special sequence II

Judging a string s Whether it's another string t The subsequence

When the longest common subsequence == s.length() when ,$$s\in t$$

Ideas
step1、dp[i][j] Express text1[0:i-1] and text2[0:j-1] The longest subsequence length of is dp[i][j]
step2、

When text1[i-1] == text2[j-1] when

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

When text1[i-1] != text2[j-1] when

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

    private boolean check(String a, String b){
    
        //  Judge a  whether   yes  b The subsequence 
        // a  Is the source string  b Yes changeable string 
        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. The longest special sequence II

 public int findLUSlength(String[] strs) {
    
        int n = strs.length;
        //  Determine whether a string is another substring 
        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;
    }