leetcode1143. 最長公共子序列

leetcode1143. 最長公共子序列
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/longest-common-subsequence

題目描述

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

示例 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, text2.length <= 1000
text1 和 text2 僅由小寫英文字符組成。

暴力遞歸

解題思路

我們用指針法:
一.先把兩個字符串轉(zhuǎn)成兩個字節(jié)數(shù)組
二.兩個指針分別卡住字符數(shù)組的最右邊
三.通過比較不斷移動指針位置,遇到相等的就加1,不等的就不加
以上是整體思路:
具體細(xì)節(jié).
先考慮base case .只有指針走到了頭,才會停止
所以base case 就是0 位置,
知道了0位置,還要考慮哪個數(shù)組在0位置.要分開判斷
然后就是普遍位置了.就是遞歸的過程了.
流程清楚了,代碼就好寫了

代碼演示

    public int longestCommonSubsequence(String text1, String text2) {
        if (text1 ==null || text2 == null || text2.length() == 0 || text1.length() == 0){
            return 0;
        }
        return process(text1.toCharArray(),text2.toCharArray(),text1.length() - 1,text2.length() - 1);
    }

    /**
     *
     * @param str1 字節(jié)數(shù)組
     * @param str2 字節(jié)數(shù)組
     * @param i 字節(jié)數(shù)組str1 的下標(biāo)
     * @param j 字節(jié)數(shù)組str2 的下標(biāo)
     * @return
     */
    public static int process(char[]str1,char[]str2,int i,int j ){
        //base case 都在0 位置
        if(i == 0 && j == 0){
            return str1[i] == str2[j] ? 1 : 0;
        }else if (i == 0){
            //i 來到 0 位置 相等直接返回1 不等還要繼續(xù)移動str2 的指針就行比較有沒有相同的
            if(str1[i] == str2[j]){
                return 1;
            }else{
                return process(str1,str2,i,j - 1);
            }
        } else if (j == 0) {
            //j來到 0 位置 相等直接返回1 不等還要繼續(xù)移動str1 的指針就行比較有沒有相同的
            if(str1[i] == str2[j]){
                return 1;
            }else{
                return process(str1,str2,i - 1,j);
            }

        }else {
            int p1 = 0;
            int p2 = 0;
            int p3 = 0;
            if(str1[i] != str2[j]){
            	//不等時 str1 的指針和 str2 的指針 分兩種情況
            	//分別進行比較
                p1 = process(str1,str2,i,j - 1);
                p2 = process(str1,str2,i - 1,j );
            }else{
            	//相等時 同時移動 子序列加1 
                p3 = 1 +   process(str1,str2,i - 1,j - 1);     
            }
            return Math.max(p1,Math.max(p2,p3));
        }
    }

動態(tài)規(guī)劃

解題思路

動態(tài)規(guī)劃就是對遞歸的改寫,把遞歸過程,變成動態(tài)規(guī)劃表生成的過程.
改寫的三個步驟:
一.通過base case 先初始化能確定的值
二.通過遞歸過程去初始化剩余的值
三,返回遞歸調(diào)用的最初始狀態(tài).

代碼演示

    /**
     * 動態(tài)規(guī)劃
     * @param text1
     * @param text2
     * @return
     */
 public static int dp(String text1, String text2){
        char[] str1 = text1.toCharArray();
        char[] str2 = text2.toCharArray();
        int N = str1.length;
        int M = str2.length;
        int[][]dp = new int[N][M];
        //根據(jù)base case 初始化
        dp[0][0] = str1[0] == str2[0] ? 1 : 0;
        //str1 來到 0 位置時
        for (int j = 1; j < M ;j++){
            dp[0][j] = str1[0] == str2[j] ? 1 : dp[0][j - 1];
        }
        //str2 來到 0 位置時
        for (int i = 1;i < N ;i++){
            dp[i][0] = str1[i] == str2[0] ? 1 : dp[i - 1][0];
        }
        for (int i = 1;i < N ;i++){
            for (int j = 1;j < M ;j++){
               
            int p1 = 0;
            int p2 = 0;
            int p3 = 0;
            if(str1[i] != str2[j]){
                p1 = dp[i][j - 1];
                p2 = dp[i - 1][j];
            }else{
                p3 = 1 + dp[i -1][j - 1];     
            }

                dp[i][j] =  Math.max(p1,Math.max(p2,p3));
            }
        }
        //返回遞歸調(diào)用的最初始狀態(tài)
        return dp[N - 1][M - 1];
    }

動態(tài)規(guī)劃專題

leetcode.486. 預(yù)測贏家

數(shù)字轉(zhuǎn)字符串,有多少種轉(zhuǎn)化結(jié)果

背包問題–填滿背包的最大價格

leetcode 322 題 零錢兌換文章來源地址http://www.zghlxwxcb.cn/news/detail-804303.html

到了這里，關(guān)于leetcode1143. 最長公共子序列-動態(tài)規(guī)劃(java)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！