题目链接：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例：
输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：
长度最长的公共子数组是 [3, 2, 1] 。
提示：
1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100
思路：
动态性的问题，最适合动态规划来解决；
//定义二维数组，表示数组A的第i位与数组B的第j位是否相等的状态，0代表不相等，1代表相等 (此处二维数组的长度为长度+1，这样定义对于极值处理有益)
var dp : [[Int]] = [[Int]](repeating: [Int](repeating:0, count: bSize+1), count: aSize+1)
动态规划三部曲：
step1:推导公式
以A数组为横坐标，B数组为纵坐标定义二维数组
二维数组图(绿色框内为二维数组)
通过二维数组图可以，dp[i][j]只能由dp[i-1][i-1]共同决定了最长公共子数组的长度是否可继续+1（红色部分）
if A[i]==B[j] 可知： dp[i][j]=dp[i-1][j-1]+1
step2:初始化
根据dp[i][j] 可知 dp[i][0] dp[0][j]的值没有多大意义，重要的是dp[i-1][j-1]
所以默认全部初始化为0即可
step3:写循环体
注意：循环体从1开始，是为了处理i-1与j-1极值的问题
时间复杂度：O(i*j)
空间复杂度：O(i*j)
func findLength(_ A:[Int], _ B:[Int]) -> Int{
let aSize = A.count
let bSize = B.count
var dp : [[Int]] = [[Int]](repeating: [Int](repeating:0, count: bSize+1), count: aSize+1)
var result : Int=0
for i in 1 ... aSize {
for j in 1 ... bSize {
if A[i-1] == B[j-1] {//此处与上面分析推导公式不一致，是因为从1开始，而非从0
dp[i][j] = dp[i-1][j-1]+1
}
result =max(dp[i][j], result)
}
}
return result
}
题目链接：
https://leetcode-cn.com/problems/longest-common-subsequence/
最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
示例 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 <= 1000
1 <= text2.length <= 1000
输入的字符串只含有小写英文字符。
思路：
定义dp数组，二维数组，横坐标为test1，纵坐标为test2
var dp:[[Int]] = [[Int]](repeating: [Int](repeating: 0, count: aSize+1), count: bSize+1)
注意：此处动态二维数组长度为aSize+1,bSize+1；是因为从1开始存储数据，0位默认位0，方便后续比较前一位内容，否则还需要判断下标越界
dp数组
动态规划三部曲：
step1:确定推导公式
通过上图可知：
dp[i][j]对应的状态值由test1[i-1] 与test2[j-1]的值决定
如果test1[i-1] = test2[j-1],那么dp[i][j] = dp[i-1][j-1] + 1
如果test1[i-1] != test2[j-1]，那么dp[i][j] = max(dp[i-1][j],dp[i][j-1])
所以推导公式为：
if test1[i-1] == test2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
}else{
dp[i][j] = max(dp[i-1][j],dp[i][j-1])
}
step2:初始化
初始化的时候不能确定二者是否有相等的字符，所以初始赋值全部为0
step3:写循环体
代码如下：
func longestCommonSubsequence(_ test1:String, _ test2: String) -> Int{
let aSize : Int= test1.count
let bSize : Int= test2.count
let test1List: [Character] = Array(test1)
let test2List: [Character] = Array(test2)
var dp:[[Int]] = [[Int]](repeating: [Int](repeating:0, count: aSize+1), count: bSize+1)
for i in 1 ... bSize {
for j in 1 ... aSize {
if test2List[i-1] == test1List[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[bSize][aSize]
}
题目链接：https://leetcode-cn.com/problems/is-subsequence/
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
示例 1：
输入：s = "abc", t = "ahbgdc"
输出：true
示例 2：
输入：s = "axc", t = "ahbgdc"
输出：false
提示：
0 <= s.length <= 100
0 <= t.length <= 10^4
两个字符串都只由小写字符组成。
思路：使用动态规划(此题与上一题类似，具体图参考上一题的图)
动态规划三部曲
1、确定推导公式(由图可知)
if tArray[j-1] == sArray[i-1] dp[i][j] = dp[i-1]+1
else dp[i][j] = max(dp[i-1][j],dp[i][j-1])
需要注意的是，字符比较的时候，需要先-1，因为数组是从索引为1的位置开始，默认第一位全部补0，便于循环，省去麻烦的极值判断
2、初始化
因为dp[i]取决于dp[i-1],所以dp[0][0] = 0
3、写循环体
具体代码如下：
func isSubsequence(_ s: String, _ t: String) -> Bool {
let sSize : Int= s.count
let tSize:Int= t.count
if sSize > tSize {
return false
}
//定义一个二维数组用来存储对应的状态，（此处声明的二维数据比原数组大1，因为后续循环要从1开始，预留一个空位，便于后续循环使用）
var dp: [[Int]] = [[Int]](repeating: [Int](repeating:0, count: tSize+1), count: sSize+1)
let sArray = Array(s)
let tArray = Array(t)
for j in 1 ... tSize {
for i in 1 ... sSize {
if tArray[j-1] == sArray[i-1] {
dp[i][j] = dp[i-1][j]+1
}else{
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
}
}
}
return dp[sSize][tSize] == sSize
}
网友评论