Question 1 - OCR

Main.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Scanner;


public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int nWords = in.nextInt();
        in.nextLine();
        
        ArrayList<String> words = new ArrayList<String>();
        for (int i = 0; i < nWords; i++) {
            words.add(in.nextLine());
        }
        
        int nDicts = in.nextInt();
        in.nextLine();
        
        ArrayList<String> dict = new ArrayList<String>();
        for (int i = 0; i < nDicts; i++) {
            dict.add(in.nextLine());
        }        
        
        for (String w : words) {
            ArrayList<String> candidates = new ArrayList<String>();
            int minLength = Integer.MAX_VALUE;
            for (String d : dict) {
                int l = distance(w, d);
                if (l < minLength) {
                    candidates.clear();
                    candidates.add(d);
                    minLength = l;
                }
                else if (l == minLength) {
                    candidates.add(d);
                }
            }
            System.out.println(minLength);
            Collections.sort(candidates);
            int printlen = Math.min(3, candidates.size());
            for (int i = 0; i < printlen; i++) {
                System.out.println(candidates.get(i));
            }
        }
    }
    
    public static int distance(String a, String b) {
        return distance(a, b, 0, 0, 0, new HashMap<String, Integer>());
    }
    
    public static int distance(String a, String b, int iA, int iB, int length, HashMap<String, Integer> memo) {
        String memoStr = iA + "," + iB + "," + length;
        if (memo.containsKey(memoStr)) {
            return memo.get(memoStr);
        }

        if (iA == a.length() && iB == b.length()) {
            memo.put(memoStr, length);
            return length;
        }
        
        if (iA < a.length() && iB < b.length() && a.charAt(iA) == b.charAt(iB)) {
            int dist = distance(a, b, ++iA, ++iB, length, memo);
            memo.put(memoStr, dist);
            return dist;
        }
        
        // Add
        int lAdd = Integer.MAX_VALUE;
        if (iB < b.length()) {
            lAdd = distance(a, b, iA, iB + 1, length + 1, memo);
        }
        
        // Remove
        int lRemove = Integer.MAX_VALUE;
        if (iA < a.length()) {
            lRemove = distance(a, b, iA + 1, iB, length + 1, memo);
        }
        
        // Replace
        int lReplace = Integer.MAX_VALUE;
        if (iA < a.length() && iB < b.length()) {
            lReplace = distance(a, b, iA + 1, iB + 1, length + 1, memo);
        }
        
        int dist = Math.min(Math.min(lAdd, lRemove), lReplace);
        memo.put(memoStr, dist);
        return dist;
    }

}