1143. 最長公共子序列

問題描述

給定兩個字符串 text1 和 text2，返回這兩個字符串的最長公共子序列的長度。
一個字符串的 子序列 是指這樣一個新的字符串：它是由原字符串在不改變字符的相對順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。兩個字符串的「公共子序列」是這兩個字符串所共同擁有的子序列。
若這兩個字符串沒有公共子序列，則返回 0。

解題思路

二維dp數(shù)組：dp[i][j]表示目標串的子串text1.substring(0, i )和text2.substring(0, j )的最長公共子序列的長度

s.substring(int beginIndex，int endIndex)截取規(guī)則：beginIndex =< s的值 < endIndex

base case：因為若其中一個子串為空，則公共子序列一定為空，所以dp數(shù)組的首行和首列均為0
狀態(tài)轉(zhuǎn)移：如果text1.charAt(i-1)==text2.charAt(j-1)，則該字符可加入公共子序列，即dp[i][j] = dp[i-1][j-1] + 1；如果text1.charAt(i)！=text2.charAt(j)，則dp[i][j]應該是dp[i-1][j]與dp[i][j-1]中的最大值。

代碼實現(xiàn)

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int l1 = text1.length(), l2 = text2.length();
        
        int[][] dp = new int[l1 + 1][l2 + 1];
        for(int i = 0; i <= l1; i++){
            //base case, text2為空時公共子序列一定為空
            dp[i][0] = 0;
            if(i == 0) continue;

            for(int j = 0; j <= l2; j++){
                //base case, text1為空時公共子序列一定為空
                dp[0][j] = 0;
                if(j == 0) continue;

                if(text1.charAt(i - 1) == text2.charAt(j - 1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }

        return dp[l1][l2];
    }
}

516. 最長回文子序列

問題描述

給定一個字符串 s ，找到其中最長的回文子序列，并返回該序列的長度。可以假設 s 的最大長度為 1000 。

解題思路

二維dp數(shù)組：dp[i][j]表示s的子串s.substring(i,j+1)的最長回文子序列長度

s.substring(int beginIndex，int endIndex)截取規(guī)則：beginIndex =< s的值 < endIndex

狀態(tài)轉(zhuǎn)移：如果s.charAt(i)==s.charAt(j)，則該字符可加入到原回文子序列兩端，即dp[i][j] = dp[i+1][j-1] + 2；如果text1.charAt(i)！=text2.charAt(j)，則dp[i][j]應該是dp[i+1][j]與dp[i][j-1]中的最大值。

class Solution {
    public int longestPalindromeSubseq(String s) {
        int l = s.length();

        int[][] dp = new int[l][l];

        for(int i = l - 1; i >= 0; i--){
            int j = 0;
            while(j < i){
                //當i>j時，substring(i,j)不存在，所以回文子序列長度為0
                dp[i][j] = 0;
                j++;
            }
            //i==j時，子串中只有一個字符時，回文子序列長度為1
            dp[i][i] = 1;
            
            for(j = i + 1; j < l; j++){
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = dp[i+1][j-1] + 2;
                }else{
                     dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }
        return dp[0][l-1];
    }
}