Самая длинная общая подпоследовательность Algorithem - попытка решения diff - PullRequest
Новая
       13

Самая длинная общая подпоследовательность Algorithem - попытка решения diff

0 голосов
/ 10 марта 2019

Для тех, кто не знает проблемы: Учитывая две последовательности, найдите длину самой длинной подпоследовательности, присутствующей в обеих из них. Подпоследовательность - это последовательность, которая появляется в том же относительном порядке, но не обязательно является смежной. Например, «abc», «abg», «bdf», «aeg», ‘« acefg », и т. Д. Являются подпоследовательностями« abcdefg ».

Я почти решил проблему по-своему, но у меня есть определенные проблемы с моим кодом для следующих входных данных: "t", "tttt" = результат будет 4, что неверно. "tttt", "tttt" = результат в порядке, но мне не нравится решение для этого, поэтому, если у кого-то есть другой способ, я бы хотел услышать.

Я понимаю проблему, но не могу найти решение, которое будет работать так, как я написал алгоритм.

вот мой код: 

    public static int lcs(String s, String t) {
    return lcs(s,t,0,0,0,0);
}

private static int lcs(String s, String t, int i, int j, int max,int count) {

    if(i == s.length() || j == t.length()) 
        return Math.max(max, count); 

    if(i != 0 && j != 0 && (s.charAt(i-1) == s.charAt(i) || t.charAt(j-1) == t.charAt(j))) 
        count--; //in case Strings are identical.

    if(s.charAt(i) == t.charAt(j)) 
        count++; 

    max = Math.max(Math.max(lcs(s,t,i,j+1,max,count), lcs(s,t,i+1,j+1,max,count)),lcs(s,t,i+1,j,max,count));
    return max;
}
...