Я пытаюсь найти самую длинную общую подстроку из двух строк, используя рекурсию и 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);
}
}
}
Это прекрасно работает. Однако есть несколько вещей, которые мне не нравятся в моем коде.
- Использование глобальной переменной (static int maxcount) для сравнения по кадрам
- Я не думаю, что это настоящее динамическое программирование или возврат с возвратом, поскольку нижний кадр не возвращает его вывод в более высокий кадр, который затем решает, что с ним делать.
Пожалуйста, поделитесь своими впечатлениями о том, как я могу добиться этого без использования глобальной переменной и с помощью отслеживания с возвратом.
PS: Мне известны другие подходы к проблеме, например, сохранение матрицы и выполнение чего-то вроде
M [i] [j] = M [i-1] [j-1] +1, если (str [i] == str [j])
Цель не в том, чтобы решить проблему, а в том, чтобы найти элегантное рекурсивное решение с возвратом.
