(SPOJ) Edit Distance - Solution

Link to the problem: http://www.spoj.com/problems/EDIST/

The solution below used a concept called Edit Distance, related to Dynamic Programming, to solve this problem.


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

class Main {
    public String s1;
    public String s2;
    public int[][] memo;
   
    public int rec(int indexS1, int indexS2) {
        if (indexS1 == s1.length()) {
            return s2.length()-indexS2;
        }
        if (indexS2 == s2.length()) {
            return s1.length()-indexS1;
        }
       
        if (memo[indexS1][indexS2] != -1) {
            return memo[indexS1][indexS2];
        }       
       
        int delete = rec(indexS1+1, indexS2)+1;
        int insert = rec(indexS1, indexS2+1)+1;
        int replace = rec(indexS1+1, indexS2+1)+(s1.charAt(indexS1) == s2.charAt(indexS2) ? 0 : 1);
           
        memo[indexS1][indexS2] = Math.min(delete, Math.min(insert, replace));
        return memo[indexS1][indexS2];
    }
   
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
                     
        memo = new int[2100][2100];
       
        int numTests = Integer.parseInt(br.readLine());
        for (int test = 0; test < numTests; test++) {
            s1 = br.readLine();
            s2 = br.readLine();
           
            for (int i = 0; i <= s1.length(); i++) {
                for (int j = 0; j <= s2.length(); j++) {
                    memo[i][j] = -1;
                }
            }
            for (int i = s1.length(); i >= 0; i--) {
                for (int j = s2.length(); j >= 0; j--) {
                    rec(i, j);
                }
            }
           
            bw.write(rec(0, 0)+"\n");
        }
       
        bw.flush();
        bw.close();
                 
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}