(UVA) AGTC - Solution

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

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


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

class Main {
    public int s1Length;
    public String s1;
    public int s2Length;
    public String s2;
    public int[][] memo;
   
    public int rec(int indexS1, int indexS2) {
        if (indexS1 == s1Length) {
            return s2Length-indexS2;
        }
        if (indexS2 == s2Length) {
            return s1Length-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 change = rec(indexS1+1, indexS2+1) + ((s1.charAt(indexS1) == s2.charAt(indexS2)) ? 0 : 1);
       
        memo[indexS1][indexS2] = Math.min(delete, Math.min(insert, change));
        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));

        String line = br.readLine();
        while (line != null) {
            String[] s = line.split(" ");
            s1Length = Integer.parseInt(s[0]);
            s1 = s[1];
            line = br.readLine();
            s = line.split(" ");
            s2Length = Integer.parseInt(s[0]);
            s2 = s[1];
           
            memo = new int[s1Length][s2Length];
            for (int i = 0; i < s1Length; i++) {
                for (int j = 0; j < s2Length; j++) {
                    memo[i][j] = -1;
                }
            }
           
            bw.write(rec(0, 0)+"\n");
           
            line = br.readLine();
        }
                                              
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}