1143. Longest Common Subsequence
Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.
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.
For example, “ace” is a subsequence of “abcde”.
A common subsequence of two strings is a subsequence that is common to both strings.
动态规划,dp的长和宽分别为两个字符串的长度。
遍历dp字符串的长和宽。(注意在第一层遍历时先保存当前选择的字符可以提升速度。)
当两个字符串相同时,则可以从上一个状态+1。
注意状态转移方程的上一个状态应该是从对角线方向+1。
当两个字符串不同时,则继续保存之前的最大长度。
1 | class Solution { |
1143. Longest Common Subsequence
https://xuanhe95.github.io/2022/05/02/1143-Longest-Common-Subsequence/