Guest User

PALINDROME

a guest
May 7th, 2018
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.37 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.util.Arrays;
  5.  
  6. import static java.lang.Integer.MAX_VALUE;
  7.  
  8. class Palindrome {
  9.  
  10.     static int dp[][] = new int[3][5000];
  11.     public static void main(String[] args) throws IOException {
  12.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  13.         int n = Integer.parseInt(br.readLine());
  14.         char[] s = br.readLine().toCharArray();
  15.         System.out.println(solve(s, n));
  16.     }
  17.  
  18.     private static int solve(char[] s, int n) {
  19.         return minCost(s, n);
  20.     }
  21.  
  22.     private static int minCost(char[] s, int n) {
  23.  
  24.         //dp[len][x] represents the min cost of making string with length len starting from x
  25.         for (int i = 0; i < n; i++) {
  26.             dp[0][i] = 0;
  27.             dp[1][i] = 0;
  28.         }
  29.         for (int len = 2; len <= n; len++) {
  30.             Arrays.fill(dp[2], 0, n, MAX_VALUE);
  31.             for (int j = 0; j + len - 1 < n; j++) {
  32.                 if (s[j] == s[j + len - 1]) {
  33.                     dp[2][j] = dp[0][j + 1];
  34.                 } else {
  35.                     dp[2][j] = 1 + Math.min(dp[1][j + 1], dp[1][j]);
  36.                 }
  37.             }
  38.             System.arraycopy(dp[1], 0, dp[0], 0, n);
  39.             System.arraycopy(dp[2], 0, dp[1], 0, n);
  40.         }
  41.         return dp[1][0];
  42.     }
  43.  
  44. }
Add Comment
Please, Sign In to add comment