(UVA) String to Palindrome - Solution 2

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1680

The solution below is an iterative version of the previous solution.


import java.io.*;
import java.util.*;

class Main {
    public String s;
    public int[][] memo;
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int numTests = sc.nextInt();
        memo = new int[1024][1024];
        for (int test = 0; test < numTests; test++) {
            s = sc.next();

            for (int i = 0; i < s.length(); i++) {
                for (int j = 0; j < s.length(); j++) {
                    memo[i][j] = -1;
                }
            }
           
            for (int d = 1; d < s.length(); d++) {
                for (int i = 0; i < s.length() -d ; i++) {
                    int min = 1000000000;
                    min = Math.min(min, memo[i][i+d-1]+1);
                    min = Math.min(min, memo[i+1][i+d]+1);
                    memo[i][i+d] = Math.min(min, memo[i+1][i+d-1]+(s.charAt(i) == s.charAt(i+d) ? 0 : 1));
                }
            }
           
            bw.write("Case " + (test+1) + ": ");
            bw.write(memo[0][s.length()-1]+"\n");
        }
                                              
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}