最长公共子序列java
时间: 2023-09-11 07:04:03 浏览: 50
最长公共子序列(Longest Common Subsequence,简称LCS)是指两个序列共同拥有的最长的子序列。在 Java 中,可以使用动态规划来求解最长公共子序列。
以下是 Java 代码示例:
```
public static String LCS(String s1, String s2) {
int m = s1.length();
int n = s2.length();
int[][] lcs = new int[m+1][n+1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0)
lcs[i][j] = 0;
else if (s1.charAt(i-1) == s2.charAt(j-1))
lcs[i][j] = lcs[i-1][j-1] + 1;
else
lcs[i][j] = Math.max(lcs[i-1][j], lcs[i][j-1]);
}
}
int index = lcs[m][n];
char[] result = new char[index];
int i = m, j = n;
while (i > 0 && j > 0) {
if (s1.charAt(i-1) == s2.charAt(j-1)) {
result[--index] = s1.charAt(i-1);
i--;
j--;
}
else if (lcs[i-1][j] > lcs[i][j-1])
i--;
else
j--;
}
return new String(result);
}
```
使用该函数时,传入两个字符串作为参数,即可得到它们的最长公共子序列。
注意,此函数仅返回最长公共子序列,而不是其长度。如果需要返回长度,只需将函数调用结果的 length 属性作为返回值即可。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)