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.
Example 1:
代码语言：javascript复制Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.Example 2:
代码语言：javascript复制Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.Example 3:
代码语言：javascript复制Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.Constraints:
1 <= text1.length, text2.length <= 1000text1andtext2consist of only lowercase English characters.
思路：
题目让求两个字符串的最大公共子序列长度，用动态规划来做，遍历两个字符串，状态转移方程：当A字符串的i位和B字符串的j位相同时候：取前一位的最优解 1 也就是A[i] = B[j] 的时候，dp[i][j] = dp[i][j] 1。 当不相同的时候，那么只需要把A字符串0~i的最优解或者B字符串0～j的最优解继承下来就行，就是dp[i][j] = max(dp[i][j-1], dp[i-1][j])。 需要注意的是这里的边界情况，可以把存状态的数组都比两个字符串大一点，就能保证走到字符串长度的时候不越界。
代码：
golang:
代码语言：javascript复制func longestCommonSubsequence(text1 string, text2 string) int {
var size1 = len(text1)
var size2 = len(text2)
var dp = make([][]int, size1 1)
for i := range dp {
dp[i] = make([]int, size2 1)
}
// 初始条件都是0
var maxSize = 0
for i := 0; i < size1; i {
for j := 0; j < size2; j {
// 因为定义的时候都保证比字符串大一位，这里直接够存就行。
if text1[i] == text2[j] {
dp[i 1][j 1] = dp[i][j] 1
} else {
dp[i 1][j 1] = max(dp[i 1][j], dp[i][j 1])
}
// 更新最大值
maxSize = max(dp[i 1][j 1], maxSize)
}
}
return maxSize
}
func max(i, j int) int {
if i < j {
return j
}
return i
}
