用java写一个最长公共子序列自顶向下的算法
时间: 2024-05-03 21:16:28 浏览: 83
java算法大全_java算法网_java_实用小算法_
好的,下面是使用Java实现最长公共子序列自顶向下的算法的示例代码:
```java
public class LongestCommonSubsequence {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] memo = new int[m][n];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
return helper(text1, text2, m - 1, n - 1, memo);
}
private int helper(String text1, String text2, int i, int j, int[][] memo) {
if (i < 0 || j < 0) {
return 0;
}
if (memo[i][j] != -1) {
return memo[i][j];
}
if (text1.charAt(i) == text2.charAt(j)) {
memo[i][j] = 1 + helper(text1, text2, i - 1, j - 1, memo);
} else {
memo[i][j] = Math.max(helper(text1, text2, i - 1, j, memo), helper(text1, text2, i, j - 1, memo));
}
return memo[i][j];
}
}
```
该算法的时间复杂度为$O(mn)$,其中$m$和$n$分别为两个字符串的长度。
阅读全文