Missing values and NPE in Levenshtein Algorithm

Question

I need to create this class, but I can't get it to work:

public void printTable(): prints table (two-dimensional array). (optional: print the table with the two words in their correct positions in the first row and first column respectively.)

public class Levenshtein {
private String word1;
private String word2;
private int[][] table;

public Levenshtein(String aWord1, String aWord2) {
    word1 = aWord1;
    word2 = aWord2;

    Levenshtein.table(word1, word2);
}

private static int[][] table(String word1, String word2) {

    int[][] distTable = new int[word1.length()+1][word2.length()+1];

    for (int i = 0; i < distTable.length; i++) {
        distTable[i][0] = i;
    }
    for (int j = 0; j < distTable[0].length; j++) {
        distTable[0][j] = j;
    }

    return distTable;

}

private static int min(int i1, int i2, int i3) {
    return Math.min(Math.min(i1, i2), i3);

}

public int distance() {
    int[][] distance = new int[word1.length() + 1][word2.length() + 1];        

    for (int i = 0; i <= word1.length(); i++)                                 
        distance[i][0] = i;                                                  
    for (int j = 1; j <= word2.length(); j++)                                 
        distance[0][j] = j;                                                  

    for (int i = 1; i <= word1.length(); i++)                                 
        for (int j = 1; j <= word2.length(); j++)                             
            distance[i][j] = min(                                        
                    distance[i - 1][j] + 1,                                  
                    distance[i][j - 1] + 1,                                  
                    distance[i - 1][j - 1] + ((word1.charAt(i - 1) == word2.charAt(j - 1)) ? 0 : 1));

    return distance[word1.length()][word2.length()];
}



public void printTable() {
    String tableArray[][] = new String[word1.length()+2][word2.length()+2];

    //Header Row
    for (int i = 0; i < word1.length()+2; i++) {
        if (i == 0 || i == 1) {
            tableArray[i][0] = "*";
        } else {
            String tmp = String.valueOf((word1.charAt(i-2)));
            tableArray[i][0] = tmp;
        }
    }
    //Header Column
    for (int j = 0; j < word2.length()+2; j++) {
        if (j == 0 || j == 1) {
            tableArray[0][j] = "*";
        } else {
            String tmp = String.valueOf((word2.charAt(j-2)));
            tableArray[0][j] = tmp;
        }
    }

    //Initialize column 0 (column 0 = header, start column = 1)
    for (int k = 1; k < tableArray.length-2; k++) {
        int tmp = k;
        tableArray[1][k] = String.valueOf(tmp-1);
    }
    for (int l = 1; l < tableArray.length-1; l++) {
        int tmp = l;
        tableArray[l][1] = String.valueOf(tmp-1);
    }
    System.out.println(tableArray[1][1]);

    //Filling Table
    for (int i = 2; i <= word1.length(); i++)   {                              
        for (int j = 2; j <= word2.length(); j++) {                         
            tableArray[i][j] = String.valueOf(min(
                    Integer.valueOf(tableArray[i - 1][j]) + 1,
                    Integer.valueOf(tableArray[i][j - 1]) + 1,
                    Integer.valueOf(tableArray[i - 1][j - 1]) + ((word1.charAt(i - 1) == word2.charAt(j - 1)) ? 0 : 1)));
        }}

    //Print Table
    for (int m = 0; m < word1.length()+2; m++) {
        //System.out.print(tableArray[m][0]);
        for (int n = 0; n < word2.length()+2; n++) {
            System.out.print(tableArray[m][n] + " | ");
        }
        if (m < word1.length()+2 ) { System.out.print("\n"); }
    }

}

}

MainClass:

public class MainClass {

    public static void main(String[] args) {

        Levenshtein lev = new Levenshtein("face", "ape");
        Levenshtein lev2 = new Levenshtein("ape", "face");

        //System.out.println(lev.distance());

        lev.printTable();
        lev2.printTable();

    }
}

This will output:

0
* | * | a | p | e | 
* | 0 | 1 | 2 | null | 
f | 1 | 1 | 2 | null | 
a | 2 | 2 | 2 | null | 
c | 3 | 3 | 2 | null | 
e | null | null | null | null | 
0
Exception in thread "main" java.lang.NumberFormatException: null
    at java.lang.Integer.parseInt(Integer.java:542)
    at java.lang.Integer.valueOf(Integer.java:766)
    at Levenshtein.printTable(Levenshtein.java:90)
    at MainClass.main(MainClass.java:11)

So in the first one it doesn't calculate the last column, and in the 2nd it just doesn't work.

Questions seeking debugging help ("why isn't this code working?") must include the desired behavior, a specific problem or error and the shortest code necessary to reproduce it in the question itself. Questions without a clear problem statement are not useful to other readers. — Michael, Nov 19 '18 at 11:41
My guess is that `Integer.valueOf` throws the `NumberFormatException` because `tableArray` contains a `null`. Could you [create a Minimal, Complete, and Verifiable example](https://stackoverflow.com/help/mcve), please? Such would be great for pinning your error down. If not, at least tell us which line is line 90 of `Levenshtein.java`, since the stacktrace says the error happens here. — Ole V.V., Nov 19 '18 at 12:16
Somehow seems related: [Printing out suggested words](https://stackoverflow.com/questions/53375777/printing-out-suggested-words) — asked nearly simultaneously. — Ole V.V., Nov 19 '18 at 19:35
Possibly half-way a duplicate of [How can I prevent java.lang.NumberFormatException: For input string: “N/A”?](https://stackoverflow.com/questions/18711896/how-can-i-prevent-java-lang-numberformatexception-for-input-string-n-a) — Ole V.V., Nov 20 '18 at 06:43
Or depending on how you see it possible duplicate of [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — Ole V.V., Nov 20 '18 at 08:24

Ole V.V. · Answer 1 · 2018-11-20T07:48:13.033

I believe there are several bugs in your program, so I am not going through all of them.

So in the first one it doesn't calculate the last column,…

tableArray is 2 cells greater in each dimension than the word lengths (6 by 5 in your first example), but the loop where you are filling the table only runs from 0 through the length of each word (5 by 4). Therefore the last row and the last column are not filled. I suspect that you are also filling the wrong values into the table. Possibly you are not using the right indices somewhere. You need to fix this and have the loop run one iteration longer.

…and in the 2nd it just doesn't work.

When filling the table, in the iteration where i is 2 and j is 3, when you are doing Integer.valueOf(tableArray[i - 1][j]), that table cell is null, which causes Integer.valueOf to throw a NumberFormatException. That cell — tableArray[1][3] — was not supposed to be null, so why is it? Row 1 was supposed to be filled higher up, in this loop:

    for (int k = 1; k < tableArray.length-2; k++) {
        int tmp = k;
        tableArray[1][k] = String.valueOf(tmp-1);
    }

But the boundary tableArray.length-2 is wrong. The table is 5 by 6 this time, so the bpoundary is 5 – 2 = 3, so only cells 0, 1 and 2 are filled, where you had wanted cells 3, 4 and 5 to be filled too. BTW the boundary in the following for loop is wrong too.

Design tips

Use only one table, your private int[][] table, throughout your class. Don’t use local tables in your methods. If you find it easier to have a table of strings in your printTable method, that is OK, but fill it from the table in the class rather than calculating its entire contents anew. It will be much simpler.

This requires that the table in the class has been filled (calculated), of course. I believe that this line in the constructor was supposed to do that?

    Levenshtein.table(word1, word2);

It doesn’t do that, though, because the table method too works on its own table, not the private int[][] table. You may fix this easily, though, by assigning the return value from the table method to the table variable (confusing that a variable and a method share the same name, you may want to change that too).

thank you for your tipps. yes i do/did a lot of mistakes but thats cuz I'm in school learning programming :) — Kamikaze, Nov 21 '18 at 07:05

Missing values and NPE in Levenshtein Algorithm

1 Answers1

Design tips