텐센트 2017 여름방학 실습생 프로그래밍 문제-구성회문열

문제풀이 사상: 이 문제는 가장 긴 공공 서열의 변형을 구하는 것이다

제목:

문자열 s를 지정하면 나머지 문자열을 회문열로 만들 수 있는 문자를 삭제할 수 있습니다.어떻게 삭제해야만 회문열을 가장 길게 할 수 있습니까?삭제할 문자 수를 출력합니다.

설명 입력:

입력 데이터가 여러 조로 되어 있으며, 각 조는 하나의 문자열s를 포함하고, 보증: 1<=s.length<=1000.

출력 설명:

각 그룹의 데이터에 대해 최소한 삭제해야 할 문자 수를 나타내는 정수를 출력합니다.

예를 입력합니다.

abcda google

출력 예:

2 2

코드:

import java.util.Scanner;

public class Palindrome {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            String str = scan.nextLine();
            System.out.println(str.length() - LCS(str));
        }
        scan.close();
    }

    private static int LCS(String str) {
        String reStr = new StringBuilder(str).reverse().toString();
        int len = str.length();
        int[][] dp = new int[len + 1][len + 1];
        for (int i = 1; i <= len; i++) {
            for (int j = 1; j <= len; j++) {
                if (str.charAt(i-1) == reStr.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else {
                    dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];
                }
            }
        }
        return dp[len][len];
    }
}