首页最长公共子串java leetcode

最长公共子串java leetcode

时间: 2025-01-21 10:16:37 浏览: 45

### Java 实现最长公共子串 LeetCode 题解对于寻找两个字符串之间的最长公共子串问题，在处理过程中通常采用动态规划方法来解决。该算法通过构建一个二维数组 `dp` 来记录两个字符串之间字符匹配的情况。具体来说，当遍历到 `text1[i-1] == text2[j-1]` 时，则有 `dp[i][j] = dp[i-1][j-1] + 1` 表明当前字符相等并延续之前的连续相同字符计数；如果不相等则设置为零因为这里关注的是连续相同的子串而非子序列[^1]。下面是一个完整的解决方案： ```java class Solution { public String longestCommonSubstring(String str1, String str2) { int m = str1.length(); int n = str2.length(); // 创建DP表 int[][] dp = new int[m + 1][n + 1]; // 记录最大长度及其结束位置 int maxLength = 0; int endIndex = -1; for (int i = 1; i <= m; ++i){ char c1 = str1.charAt(i - 1); for (int j = 1; j <= n; ++j){ char c2 = str2.charAt(j - 1); if(c1 == c2){ dp[i][j] = dp[i - 1][j - 1] + 1; if(dp[i][j] > maxLength){ maxLength = dp[i][j]; endIndex = i - 1; } }else{ dp[i][j] = 0; } } } // 如果找到了有效结果就截取出来作为最终答案 return maxLength != 0 ? str1.substring(endIndex - maxLength + 1,endIndex + 1): ""; } } ``` 此代码实现了上述逻辑，并能够有效地找出给定两字符串间的最长公共子串。注意这里的实现方式与最长公共子序列不同之处在于一旦遇到不匹配即重置计数值为零以确保只考虑连续部分[^3]。

阅读全文