[LeetCode] 1143. Longest Common Subsequence 最長公共子序列

2021-03-02 刷盡天下

Given two strings text1 and text2, return the length of their longest common subsequence.

A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, "ace" is a subsequence of "abcde" while "aec" is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

Example 1:

Input: text1 = "abcde", text2 = "ace"

Output: 3

Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"

Output: 3

Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"

Output: 0

Explanation: There is no such common subsequence, so the result is 0.

Constraints:

這道題讓求最長相同的子序列,注意是子序列,不是子串,所以字符並不需要相連,但是字符順序還是需要保持的。LeetCode 之前也有題目需要藉助求 LCS 來解題,比如 Delete Operation for Two Strings,當時博主還疑惑怎麼 LeetCode 中沒有專門求 LCS 的題呢,這不,終於補上了。解題思路和上面那道是一模一樣,若搞懂了那道題,這道也就是沒什麼難度了,這裡是用動態規劃 Dynamic Programing 來做,使用一個二維數組 dp,其中 dp[i][j] 表示 text1 的前i個字符和 text2 的前j個字符的最長相同的子序列的字符個數,這裡大小初始化為 (m+1)x(n+1),這裡的m和n分別是 text1 和 text2 的長度。接下來就要找狀態轉移方程了,如何來更新 dp[i][j],若二者對應位置的字符相同,表示當前的 LCS 又增加了一位,所以可以用 dp[i-1][j-1] + 1 來更新 dp[i][j]。否則若對應位置的字符不相同,由於是子序列,還可以錯位比較,可以分別從 text1 或者 text2 去掉一個當前字符,那麼其 dp 值就是 dp[i-1][j] 和 dp[i][j-1],取二者中的較大值來更新 dp[i][j] 即可,最終的結果保存在了 dp[m][n] 中,參見代碼如下:

class Solution {public:    int longestCommonSubsequence(string text1, string text2) {        int m = text1.size(), n = text2.size();        vector<vector<int>> dp(m + 1, vector<int>(n + 1));        for (int i = 1; i <= m; ++i) {            for (int j = 1; j <= n; ++j) {                if (text1[i - 1] == text2[j - 1]) {                    dp[i][j] = dp[i - 1][j - 1] + 1;                } else {                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);                }            }        }        return dp[m][n];    }};

討論:這道題跟之前那道 Longest Palindromic Subsequence 的解題思路幾乎是一模一樣,你品,你細品,一定要通過現象看本質,才能舉一反三,觸類旁通。

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1143

類似題目:

Longest Palindromic Subsequence

Delete Operation for Two Strings

Shortest Common Supersequence

參考資料:

https://leetcode.com/problems/longest-common-subsequence/

https://leetcode.com/problems/longest-common-subsequence/discuss/348884/C%2B%2B-with-picture-O(nm)

https://leetcode.com/problems/longest-common-subsequence/discuss/351689/JavaPython-3-Two-DP-codes-of-O(mn)-and-O(min(m-n))-spaces-w-picture-and-analysis

LeetCode All in One 題目講解匯總(持續更新中...)

相關焦點

  • [LeetCode] 1027. Longest Arithmetic Subsequence 最長的等差數列
    subsequence in A.Example 2:Input: A = [9,4,7,2,10]Output: 3Explanation:The longest arithmetic subsequence is [4,7,10].
  • 算法總結:最長上升子序列(LIS)
    最長上升子序列,英文名 Longest Increasing Subsequence,簡稱 LIS,在面試中屬於難度較大,但又非常高頻的題目。最長遞增子序列(https://leetcode-cn.com/problems/longest-increasing-subsequence/)總體思路如果你不知道最長上升子序列是什麼意思,也沒有做那道題,我——當然不會怪你 😊最長上升(遞增)子序列這道題是最最基本的,也是最常考的題了,其他題目都是由它衍生而來。
  • LeetCode-14. Longest Common Prefix | 最長公共前綴
    common prefix string amongst an array of strings.If there is no common prefix, return an empty string "".
  • 坐標型動態規劃之:Longest Increasing Subsequence
    increasing subsequence.For example, Given [10, 9, 2, 5, 3, 7, 101, 18],The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4.
  • 最長公共前綴 | Leetcode題解
    題目描述:編寫一個函數來查找字符串數組中的最長公共前綴。如果不存在公共前綴,返回空字符串 "" 。思路1:當字符串數組長度為 0 時則公共前綴為空,直接返回令最長公共前綴 ans 的值為第一個字符串,進行初始化遍歷後面的字符串,依次將其與 ans 進行比較,兩兩找出公共前綴,最終結果即為最長公共前綴如果查找過程中出現了 ans 為空的情況,則公共前綴不存在直接返回時間複雜度:O(s)O(s)O(s),s 為所有字符串的長度之和思路2:當字符串數組長度為 0 時則公共前綴為空,直接返回令最長公共前綴
  • Longest Continuous Increasing Subsequence
    題目URL:https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence
  • LeetCode 例題精講 | 15 最長公共子序列:二維動態規劃的解法
    轉自面向大象編程本期例題:LeetCode 1143. Longest Common Subsequence 最長公共子序列(Medium)給定兩個字符串 s 和 t,返回這兩個字符串的最長公共子序列的長度。若這兩個字符串沒有公共子序列,則返回 0。
  • 雖然你看過,但就是寫不出來系列-最長上升(下降)子序列並輸出子序列
    任何疑問、意見、建議請公眾號留言或聯繫qq474356284    給定一個無序的整數數組,找到其中最長上升子序列的長度。
  • 最長回文子串 | Leetcode題解
    題目描述給定一個字符串 s,找到 s 中最長的回文子串。你可以假設  s 的最大長度為 1000。,要我們求出給定字符串的最大回文子串。,枚舉所有長度大於等於 22 的子串,依次判斷它們是否是回文;在具體實現時,可以只針對大於「當前得到的最長回文子串長度」的子串進行「回文驗證」;在記錄最長回文子串的時候,可以只記錄「當前子串的起始位置」和「子串長度」,不必做截取。
  • leetcode-14. Longest Common Prefix
    題目描述(簡單難度)編寫一個函數來查找字符串數組中的最長公共前綴。如果不存在公共前綴,返回空字符串 ""。解法三 遞歸我們把原來的數組分成兩部分,求出左半部分的最長公共前綴,求出右半部分的最長公共前綴,然後求出的兩個結果再求最長公共前綴,就是最後的結果了。
  • 詳解最長公共子序列問題,秒殺三道動態規劃題目
    動態規劃系列問題也是一樣,尤其是子序列相關的問題。本文從「最長公共子序列問題」展開,總結三道子序列問題,解這道題仔細講講這種子序列問題的套路,你就能感受到這種思維方式了。最長公共子序列計算最長公共子序列(Longest Common Subsequence,簡稱 LCS)是一道經典的動態規劃題目,大家應該都見過:給你輸入兩個字符串s1和s2,請你找出他們倆的最長公共子序列,返回這個子序列的長度。
  • leetcode第14題-最長公共前綴
    編寫一個函數來查找字符串數組中的最長公共前綴。如果不存在公共前綴,返回空字符串 ""。示例 1:輸入: ["flower","flow","flight"]輸出: "fl"示例 2:輸入: ["dog","racecar","car"]輸出: ""解釋: 輸入不存在公共前綴。
  • Leetcode題解 LongestIncreasingSubsequence
    比如,整數數組[10, 9, 2, 5, 3, 7, 101, 18],最長遞增子序列是[2, 3, 7, 101],因此長度為4。  最長遞增子序列可能不只一個,返回長度即可。  最長遞增子序列一定是以數組中某個數字結尾的,找出以數組中每個數字結尾的最長遞增子序列後,從這些遞增子序列中找出長度最大的遞增子序列就是整個數組中最長的遞增子序列。
  • 經典動態規劃問題:最長公共/遞增子序列
    在講具體問題之前我們先來舉個例子看一下什麼是子序列(subsequence)以及它和子數組(subarray)和子集(subset)之間的區別。假設我們有一個數組:[1, 2, 3, 4, 5]。[1,2,3]是一個子序列,同時也是一個子數組。
  • 動態規劃刷題篇(1) 斐波那契、爬樓梯、路徑與最長遞增子序列
    DP數組是用來存儲當前問題的子問題的這樣一個數組。動態規劃的核心就在於:當前問題可以分解為幾個子問題。最長遞增子序列給你一個整數數組 nums ,找到其中最長嚴格遞增子序列的長度子序列是由數組派生而來的序列,刪除(或不刪除)數組中的元素而不改變其餘元素的順序。例如,[3,6,2,7] 是數組 [0,3,1,6,2,2,7] 的子序列。
  • [leetcode] 14. Longest Common Prefix
    Write a function to find the longest common prefix string amongst an array of strings.今天的題目是找出所有字符串的公共前綴,題目難度為easy。
  • Go 實現 LeetCode 全集
    /coin-change/[X] Longest Increasing Subsequence - https://leetcode.com/problems/longest-increasing-subsequence/[X] Longest Common Subsequence - https://leetcode.com/problems/longest-common-subsequence
  • 動態規劃求解最長公共子序列
    最長公共子序列最長公共子序列,英文為Longest Common Subsequence,縮寫LCS。一個序列,如果是某兩個或多個已知序列的最長子序列,則稱為最長公共子序列。另外,要注意的是最長公共子序列與最長公共子串不一樣,下面看一個例子就明白。有序列S1和S2,其中S1=hello,S2=hero。那麼最長公共子序列為heo,而最長公共子串為he。
  • 第五題:最長回文子串【leetcode】
    給定一個字符串 s,找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。
  • 動態規劃解最長公共子序列問題
    1 最長公共子序列問題概述1.1 問題定義序列是兩個序列的最長公共子序列在求得最長公共子序列 seq1,vector<int>lcs , int i,int j,int MaxLen,vector<vector<int>>&LcsSet);public:    /**     * 對外的接口     * 輸入是兩個序列     * 輸出是0-n條最長公共子序列     */