0

I'm once again searching for a strange issue :)

I've been running a algorithm to calculate a distance of Levenshtein which seemed to work fine until a client started to have issues on a very small amount of his customers. (We're talking about 1 out of a 100.000)

Until now it also only happened on Android 6, but I can't see why it should help when watching the issue.

So I'm using among the rest of my code this function:

public static int computeLevenshteinDistance(String str1, String str2)
{
    int strLen1 = str1.length();
    int strLen2 = str2.length();

    int[][] distance = new int[strLen1 + 1][strLen2 + 1];

    for (int i = 0; i <= strLen1; ++i)
    {
        distance[i][0] = i;
    }

    for (int j = 1; j <= strLen2; ++j)
    {
        distance[0][j] = j;
    }

    for (int i = 1; i <= strLen1; ++i)
    {
        for (int j = 1; j <= strLen2; ++j)
        {
            distance[i][j] = minimum(
                    distance[i - 1][j] + 1,
                    distance[i][j - 1] + 1,
                    distance[i - 1][j - 1] + ((str1.charAt(i - 1) == str2.charAt(j - 1)) ? 0 : 1));
        }
    }

    return distance[strLen1][strLen2];
}

And what sometimes goes wrong is distance[i][0] = i; which causes:

Caused by java.lang.ArrayIndexOutOfBoundsException: length=0; index=0

I'm a bit phased there since I can't see how my array could have a length of 0 being initialized as String.length + 1.

I tested many things, and strings in many languages, but I can't make it crash. It might be something very obvious I'm completely missing, but I can't see what.

Can someone point me to what's wrong?

Thanks a lot!

Edits: @cricket_007 : Syntax for creating a two-dimensional array

@Tunaki : I'm allocating my 2d array with size of string + 1, this is why I'm really surprised to see and out of bound with "length=0; index=0", since it should at least be [1][1]

@Mister Smith : Thanks for that :)

Community
  • 1
  • 1
SeikoTheWiz
  • 853
  • 1
  • 10
  • 27
  • When you make a 2d array, only the first dimension gets allocated. You must loop over it and make `new int[size]` in each index – OneCricketeer May 30 '16 at 15:58
  • @Tunaki, he knows what a `ArrayIndexOutOfBoundsException` is, he's asking how could it possibly happen. Or should SO just ban all questions with the keyword `ArrayIndexOutOfBoundsException`? /s – Martin Konecny May 30 '16 at 16:02
  • @MartinKonecny There is only one answer for an `ArrayIndexOutOfBoundsException`. You access an array with an index that is out of bounds. Such an exception needs to comes with a serious [mcve]. `strLen1` or `strLen2` are wrong, OP needs to debug. And, by the way, if OP truly knew what it was, they wouldn't be asking this question... – Tunaki May 30 '16 at 16:04
  • Just FYI, Apache Commons's [StringUtils](https://commons.apache.org/proper/commons-lang/apidocs/org/apache/commons/lang3/StringUtils.html) has two methods `getLevenshteinDistance`. – Mister Smith May 30 '16 at 16:38

0 Answers0