编写java一个方法longestSubsequence(Strings1,Strings2),该方法返回String的最大长度,String是s1和s2的公共子字符串。例如,如果s1=“industry”,s2=“conduct”,则该方法应返回3,即最长公共子字符串“ndu”的长度。
时间: 2023-05-29 11:06:47 浏览: 42
下面是一种可能的实现方式:
```java
public static int longestSubsequence(String s1, String s2) {
int m = s1.length();
int n = s2.length();
int[][] dp = new int[m+1][n+1];
int maxLen = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i-1) == s2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
if (dp[i][j] > maxLen) {
maxLen = dp[i][j];
}
} else {
dp[i][j] = 0;
}
}
}
return maxLen;
}
```
这个方法使用动态规划来解决问题,具体思路如下:
- 定义一个二维数组dp,其中dp[i][j]表示s1的前i个字符和s2的前j个字符的最长公共子字符串长度。
- 初始化dp数组,将所有元素设为0。
- 从左到右、从上到下遍历dp数组,对于每个位置(i, j),分两种情况:
- 如果s1的第i个字符等于s2的第j个字符,那么dp[i][j]就等于dp[i-1][j-1]加1,即s1的前i-1个字符和s2的前j-1个字符的最长公共子字符串长度加1。同时,如果dp[i][j]大于当前最大长度maxLen,就更新maxLen的值。
- 如果s1的第i个字符不等于s2的第j个字符,那么dp[i][j]就设为0,表示s1的前i个字符和s2的前j个字符没有公共子字符串。
- 遍历完dp数组之后,maxLen就是最长公共子字符串的长度,将其返回即可。
这个方法的时间复杂度是O(mn),其中m和n分别是s1和s2的长度。空间复杂度也是O(mn),因为需要维护一个二维数组。