【dp】構造回文

文書を作成
タイトル
文字列sを指定すると、残りの列がエコー列になるように、いくつかの文字を削除できます.どのように削除して文字列を最も長くすることができますか?削除する文字数を出力します.
説明を入力:
入力データには複数のグループがあり、各グループには1つの文字列sが含まれ、保証:1<=s.length<=1000である.
出力の説明:
データのセットごとに、削除する必要のある文字の数を表す整数を出力します.
入力例1:
abcda google
出力例1:
2 2
問題解
この問題は最も大きいサブシーケンスの問題型(LCS)の変種を探して、私達は文字列を反転することができて、正の順序と逆の順序の文字列のlcsを求めて、探したシーケンスは最も長い回文のシーケンスで、それから元の文字列の長さでこのlcsの長さを減らして、削除する文字の個数です.
どのようにlcsを探しますか?これはありふれた問題で,もう余計なことは言わない.まだ理解していないパートナーは、次のように移動できます.https://blog.csdn.net/hrn1216/article/details/51534607
次は私のコードです.比較ピットの1つは、入力された文字列を取得する際にsc.nextLine()を使用しなければならず、sc.next()を使用することはできません.そうしないと、配列の境界を越えて報告されます.個人的には、入力にスペースがある可能性があります.nextLine()を使用すると、1行を完全に読み取ることができます.next()はできません.

import java.util.*;

public class Main{
    //   、     LCS  
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while( sc.hasNextLine() ){
            String str1 = sc.nextLine();
            String str2 = new StringBuilder(str1).reverse().toString();
            int lcs = getLCS(str1, str2);
            System.out.println(str1.length()-lcs);
        }
        sc.close();
    }

    //         
    private static int getLCS(String str1, String str2){
        int len1 = str1.length();
        int len2 = str2.length();
        if( len1==0 || len2==0 ) return 0;
        int[][] dp = new int[len1+1][len2+1];

        for( int i=1; i<=len1; i++ ){
            for( int j=1; j<=len2; j++ ){
                if( str1.charAt(i-1)==str2.charAt(j-1) ){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    //       ，    dp  ，
                    //         dp[i-1][j] dp[i][j-1]     
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[len1][len2];
    }
}