이동 : 다시

Question

내 코드를 추적 긴 일반적인 서브는 LCS의 길이를 계산 작동하지만 다음 링크상의 LCS를 읽기 위해

http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

을 동일한 코드를 적용하지만 일부 문자열이 누락 . 제가 누락 된 부분을 말씀해 주시겠습니까?

구글 놀이터 링크 : 미리 http://play.golang.org/p/qnIWQqzAf5

func Back(table [][]int, str1, str2 string, i, j int) string { 
    if i == 0 || j == 0 { 
    return "" 
    } else if str1[i] == str2[j] { 
    return Back(table, str1, str2, i-1, j-1) + string(str1[i]) 
    } else { 
    if table[i][j-1] > table[i-1][j] { 
     return Back(table, str1, str2, i, j-1) 
    } else { 
     return Back(table, str1, str2, i-1, j) 
    } 
    } 
} 

감사합니다.

Answer 1

색인 생성에 문제가 있다고 생각합니다. 0 - len-1에서 문자열을 인덱싱하는 경우 테이블의 행과 열 수는 문자열 길이보다 커야합니다. LCS의 길이를 계산할 때 계산 된 것으로 보이지만 LCS를 리턴 할 때는 계산하지 않은 것 같습니다. i 및 j은 정확하게 문자열의 색인을 나타내지 만 테이블의 문자는 나타내지 않습니다.이 값은 i/j보다 커야합니다. str1[0] 및 str2[0]이 유효한 문자

는 그래서 공에 대한 검사의 당신의 기본 조건이 잘못

그래서 코드은 다음과 같은 모양입니다 : 여기

func Back(table [][]int, str1, str2 string, i, j int) string { 
    if i == -1 || j == -1 { 
    return "" 
    } else if str1[i] == str2[j] { 
    return Back(table, str1, str2, i-1, j-1) + string(str1[i]) 
    } else { 
    if table[i+1][j] > table[i][j+1] { 
     return Back(table, str1, str2, i, j-1) 
    } else { 
     return Back(table, str1, str2, i-1, j) 
    } 
    } 
} 

가 Live Code