class FastSpell{
    private String w;
    private int[][] memo; // store 1 + cost 
    // -- then zero signifies unitialised

    public FastSpell(String s){
        w = s;
    }

    int spell(String s, int i, int j) {
        int m =  memo[i][j];
        if (m > 0) //already computed this
            return (m-1);
        else{
            if (j == w.length()) {
                m = s.length() - i;
            } else if (i == s.length()) {
                m = w.length() - j;
            } else if (s.charAt(i) == w.charAt(j)) {
                m = spell(s,i+1,j+1);
            } else {
                int ins = spell(s,i,j+1);
                int del = spell(s,i+1,j);
                if (ins > del) {
                    m = del + 1;
                } else {
                    m = ins + 1;
                }
            }
            memo[i][j] = m + 1;
            return m;
        }
    }

    public int spell(String s) {
        memo = new int[1 + s.length()][1 + w.length()];
        return spell(s,0,0);
    }
}