编写一个方法longestSubsequence(Strings1,Strings2),该方法返回String的最大长度,String是s1和s2的公共子字符串。例如,如果s1=“industry”,s2=“conduct”,则该方法应返回3,即最长公共子字符串“ndu”的长度。
时间: 2023-05-29 08:06:44 浏览: 54
以下是Python的实现代码:
def longestSubsequence(s1, s2):
m = len(s1)
n = len(s2)
dp = [[0] * (n+1) for i in range(m+1)]
ans = 0
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
ans = max(ans, dp[i][j])
else:
dp[i][j] = 0
return ans
# 测试
print(longestSubsequence("industry", "conduct")) # 输出 3
相关问题
编写java一个方法longestSubsequence(Strings1,Strings2),该方法返回String的最大长度,String是s1和s2的公共子字符串。例如,如果s1=“industry”,s2=“conduct”,则该方法应返回3,即最长公共子字符串“ndu”的长度。
下面是一种可能的实现方式:
```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),因为需要维护一个二维数组。
c语言编写函数比较字符串大小,若有两个字符串s1和s2,s1与s2相等返回0,s1>s2返回1,s1<s2返回-1。
可以使用strcmp函数来比较两个字符串的大小,该函数在string.h头文件中定义。strcmp函数返回值为整型,如果s1>s2,返回正数;如果s1=s2,返回0;如果s1<s2,返回负数。
下面是一个示例代码:
```c
#include <stdio.h>
#include <string.h>
int compare_strings(char s1[], char s2[]) {
int result = strcmp(s1, s2);
if(result > 0) {
return 1;
} else if(result == 0) {
return 0;
} else {
return -1;
}
}
int main() {
char s1[] = "hello";
char s2[] = "world";
int result = compare_strings(s1, s2);
printf("%d", result);
return 0;
}
```
输出结果为-1,表示s1<s2。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)