(SPOJ) Edit Distance Again - Solution 1

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

The solution below used Dynamic Programming to solve this problem.


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

class Main {
    public String s;
    public int[][] memo;

    public int f(char c) {
        return (c >= 'A' && c <= 'Z') ? 1 : 0;
    }   

    public int rec(int index, int last) {
        if (index == s.length()) {
            return 0;
        }
   
        if (memo[index][last] != -1) {
            return memo[index][last];
        }
       
        // last == 0 -> last character was upper
        // last == 1 -> last character was lower
        int sum = 0;
        sum = rec(index+1, (last+1)%2) + (last == f(s.charAt(index)) ? 1 : 0);
       
        memo[index][last] = sum;
        return memo[index][last];
    }
   
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
                     
        s = br.readLine();
        while (s != null) {
            memo = new int[s.length()+1][2];
            for (int i = 0; i < s.length()+1; i++) {
                for (int j = 0; j < 2; j++) {
                    memo[i][j] = -1;
                }
            }
           
            bw.write(Math.min(rec(0, 0), rec(0, 1))+"\n"); // check for the first letter being considered upper-case or lower-case
              
            s = 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);
    }
}