1
2
3
4
5
|
对于两个字符串,请设计一个高效算法,求他们的最长公共子序列的长度,这里的最长公共子序列定义为有两个序列U1,U2,U3...Un和V1,V2,V3...Vn,其中Ui<Ui+1,Vi<Vi+1。且A[Ui] == B[Vi]。 给定两个字符串A和B,同时给定两个串的长度n和m,请返回最长公共子序列的长度。保证两串长度均小于等于300。 测试样例: "1A2C3D4B56",10,"B1D23CA45B6A",12 返回:6 |
题意:动态规划经典问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public static int findLCS(String A, int n, String B, int m) {
// write code here
//dp[i][j]表示A的前i个字符和B的前j个字符组成的最长公共子序列长度
int [][] dp= new int [n+ 1 ][m+ 1 ];
for ( int i= 0 ;i<=n;i++)dp[i][ 0 ]= 0 ;
for ( int j= 0 ;j<=m;j++)dp[ 0 ][j]= 0 ;
for ( int i= 1 ;i<=n;i++)
for ( int j= 1 ;j<=m;j++)
if (A.charAt(i- 1 )!=B.charAt(j- 1 )){
dp[i][j]=Math.max(dp[i][j- 1 ],dp[i- 1 ][j]);
} else {
dp[i][j]=dp[i- 1 ][j- 1 ]+ 1 ;
}
return dp[n][m];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public static int findLCS2(String A, int n,String B, int m){
int [][] dp= new int [n][m];
dp[ 0 ][ 0 ]=A.charAt( 0 )==B.charAt( 0 )? 1 : 0 ;
//dp[i][j]表示A[0..i]和B[0...j]的最长公共子序列长度
for ( int i= 1 ;i<n;i++){
dp[i][ 0 ]=Math.max(A.charAt(i)==B.charAt( 0 )? 1 : 0 ,dp[i- 1 ][ 0 ]);
}
for ( int j= 1 ;j<m;j++){
dp[ 0 ][j]=Math.max(A.charAt( 0 )==B.charAt(j)? 1 : 0 ,dp[ 0 ][j- 1 ]);
}
for ( int i= 1 ;i<n;i++)
for ( int j= 1 ;j<m;j++){
dp[i][j]=Math.max(dp[i- 1 ][j], dp[i][j- 1 ]);
if (A.charAt(i)==B.charAt(j)){
dp[i][j]=dp[i- 1 ][j- 1 ]+ 1 ;
}
}
return dp[n- 1 ][m- 1 ];
}
|
O(mn)
本文转自 努力的C 51CTO博客,原文链接:http://blog.51cto.com/fulin0532/1903586