我正在尝试使用递归和 DP 找到两个字符串的最长公共子字符串。请注意，我指的不是最长连续子序列。所以，如果两个字符串是
String s1 = "abcdf"; String s2 = "bzcdf"
Longest Common Substring == "cdf" (not "bcdf").
Basically they have to be continuous elements
我正在尝试使用递归和回溯来做到这一点。但是，问题是，如果我使用如下递归，+1会在帧中预先添加，即在调用堆栈中更高，并且不知道要出现的字符是否确实是连续元素。因此，按照上面的例子，“bcdf”就是答案。
public class ThisIsLongestCommonSubsequence_NotSubstring {
public static void main(String[] args) {
String s1 = "abcdgh";
String s2 = "abefgh";
System.out.println(fun(s1, s1.length()-1, s2, s2.length()-1));
}
static int fun(String s1, int i, String s2, int j)
{
if(i == -1 || j == -1)
return 0;
int ret = 0;
if(s1.charAt(i) == s2.charAt(j))
ret = fun(s1, i-1, s2, j-1) + 1;
else
ret = max(fun(s1, i-1, s2, j), fun(s1, i, s2, j-1));
return ret;
}
static int max(int a, int b)
{
return a>b?a:b;
}
}
至于现在，下面的代码是我想出的。请注意，每次发现不匹配时，我都会将计数重置为 0。并使用名为int count的变量跟踪匹配字符的数量，并使用名为int maxcount的变量记录程序中任何点的最高值。我的代码如下。
public class LongestContinuousSubstringGlobalvariable {
static int maxcount = 0;
public static void main(String[] args) {
String s1 = "abcdghijl";
String s2 = "abefghijk";
fun(s1, s2, s1.length()-1, s2.length()-1, 0);
System.out.println("maxcount == "+maxcount);
}
static void fun(String s1, String s2, int i, int j, int count)
{
if(i == -1 || j==-1)
return;
if(s1.charAt(i) == s2.charAt(j))
{
if(count+1 > maxcount)
maxcount = count+1;
fun(s1, s2, i-1, j-1, count+1);
}
else
{
fun(s1, s2, i-1, j, 0);
fun(s1, s2, i, j-1, 0);
}
}
}
这工作正常。但是，我不喜欢我的代码的几件事
- 使用全局变量（静态 int maxcount）跨帧进行比较
- 我不认为这是真正的动态编程或回溯，因为较低的帧没有将其输出返回到较高的帧，然后决定如何处理它。
请给我您的意见，说明如何在不使用全局变量和使用回溯的情况下实现这一目标。
PS：我知道解决该问题的其他方法，例如保留矩阵并执行类似的操作
M[i][j] = M[i-1][j-1]+1 如果（str[i] == str[j]）
目标不是解决问题，而是找到一个优雅的递归/回溯解决方案。