Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.util.Arrays;
- import static java.lang.Integer.min;
- /**
- * Created by bugkiller on 10/02/18.
- */
- class Aibohphobia {
- static int[][] dp = new int[6101][6101];
- public static void main(String[] args) throws IOException {
- BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
- int t = Integer.parseInt(br.readLine());
- while (t-- > 0) {
- char[] s = br.readLine().toCharArray();
- System.out.println(solve(s, s.length));
- }
- }
- private static int solve(char[] s, int n) {
- for (int i = 0; i < n; i++) {
- Arrays.fill(dp[i], 0, n, -1);
- }
- return minCost(s, 0, n - 1);
- }
- private static int minCost(char[] s, int start, int end) {
- if (start >= end)
- return 0;
- if (dp[start][end]!=-1)
- return dp[start][end];
- if (s[start]==s[end])
- dp[start][end] = minCost(s, start + 1, end - 1);
- else
- dp[start][end] = 1 + min(minCost(s, start, end - 1), minCost(s, start + 1, end));
- return dp[start][end];
- }
- }
Add Comment
Please, Sign In to add comment