最长公共子序列穷举法Java
时间: 2024-03-30 11:31:55 浏览: 25
最长公共子序列(Longest Common Subsequence,简称LCS)是指在两个序列中找到最长的公共子序列的问题。穷举法是一种解决LCS问题的方法之一。
穷举法的基本思想是通过遍历所有可能的子序列,然后比较它们的长度和内容,找到最长的公共子序列。
以下是使用穷举法解决LCS问题的Java代码示例:
```java
public class LCS {
public static String findLCS(String str1, String str2) {
int m = str1.length();
int n = str2.length();
int[][] dp = 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) {
dp[i][j] = 0;
} else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
int lcsLength = dp[m][n];
char[] lcsChars = new char[lcsLength];
int i = m, j = n;
while (i > 0 && j > 0) {
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
lcsChars[lcsLength - 1] = str1.charAt(i - 1);
i--;
j--;
lcsLength--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
return new String(lcsChars);
}
public static void main(String[] args) {
String str1 = "ABCDGH";
String str2 = "AEDFHR";
String lcs = findLCS(str1, str2);
System.out.println("最长公共子序列为:" + lcs);
}
}
```
上述代码中,我们使用动态规划的思想,通过构建一个二维数组dp来记录最长公共子序列的长度。然后,我们根据dp数组的内容,回溯得到最长公共子序列。
相关推荐
![](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)