社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。
一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。
例如,“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-common-subsequence
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解:
此题可以用dp解决:
定义:
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]为区间
[
1
,
i
)
[1,i)
[1,i)text1字符串和区间
[
1
,
j
)
[1,j)
[1,j)text2字符串的最长公共子序列的长度(这里假设字符串下标从1开始)
状态划分:
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]状态可以划分为
2包含4,3也包含4,不过没关系我们求最大值就行
所以求
m
a
x
(
d
p
[
i
−
1
]
[
j
]
,
d
p
[
i
]
[
j
−
1
]
,
d
p
[
i
−
1
]
[
j
−
1
]
+
1
)
max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+1)
max(dp[i−1][j],dp[i][j−1],dp[i−1][j−1]+1)的最大值就可以
但是
d
p
[
i
−
1
]
[
j
−
1
]
+
1
dp[i-1][j-1]+1
dp[i−1][j−1]+1不一定存在,只有当text1[i]和text[j]都在子序列中才可以,所以我们要判断一下,在题中坐标是以0开始的,所以判断 if(text1[i-1]==text2[j-1]) 就可以
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int t1 = text1.size();
int t2 = text2.size();
vector<vector<int>> f(t1+1,vector<int>(t2+1));
for(int i=1; i<=t1; ++i){
for(int j=1; j<=t2; ++j){
f[i][j] = max(f[i-1][j],f[i][j-1]);
if(text1[i-1]==text2[j-1]){
f[i][j] = max(f[i][j],f[i-1][j-1]+1);
}
}
}
return f[t1][t2];
}
};
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!