Чередование двух строк И индексов печати (DP)

Я пытаюсь расширить следующее решение проблемы чередования двух строк:

public static boolean isInterleave(String s1, String s2, String s3) {
    if (s3.length() == 0 && s1.length() == 0 && s2.length() == 0)
        return true;
    else if (s3.length() != s1.length() + s2.length())
        return false;

    boolean isInter[][] = new boolean[s1.length()+1][s2.length()+1];
    isInter[0][0] = true;
    for ( int i = 1; i <= s1.length(); ++i){
        if (s1.charAt(i-1) == s3.charAt(i-1))
            isInter[i][0] = true;
        else
            break;
    }
    for ( int i = 1; i <= s2.length(); ++i){
        if (s2.charAt(i-1) == s3.charAt(i-1))
            isInter[0][i] = true;
        else
            break;
    }
    // DP
    for ( int i = 1; i <= s1.length(); ++i){
        for ( int j = 1; j <= s2.length(); ++j){
            if (s3.charAt(i+j-1) == s1.charAt(i-1))
                isInter[i][j] = isInter[i-1][j] || isInter[i][j];
            if (s3.charAt(i+j-1) == s2.charAt(j-1))
                isInter[i][j] = isInter[i][j-1] || isInter[i][j];
        }
    }
    return isInter[s1.length()][s2.length()];
}

Я хотел бы напечатать индексы подпоследовательности s3, равной строке s1.

0 ответов

Другие вопросы по тегам