java - 尝试复制矩阵时出现 ArrayIndexOutOfBoundsException

Question

我正在制作一个根据字典检查单词的程序，该程序根据字典中的单词检查单词中的每个字母。 我想通过将每个差异保存在矩阵中来优化它，然后如果该单词有一些相同的字符，则将其复制到下一个单词，这样程序就不必重新计算所有内容。但是，在我当前的解决方案中，我得到了 ArrayIndexOutOfBoundsException，但我没有看到问题。

import java.util.LinkedList;
import java.util.List;
import java.util.Arrays;

public class ClosestWords {
    LinkedList<String> closestWords = null;

    static int [][] SaveVal;
    int closestDistance = -1;
    static String savedWord;
    static String savedWrongWord;

    int partDist(String w1, String w2, int w1len, int w2len, int [][] SaveVal) {

        if (w1len == 0) {
            //return w2len;
            //SaveVal[0][w2len] = w2len;
            return w2len;
        }
        else if (w2len == 0) {
            //return w1len;
            //SaveVal[w1len][0] = w1len;
            return w1len;
        }
        else if(SaveVal[w1len-1][w2len-1] != 0) {
            return SaveVal[w1len-1][w2len-1];
        }

        int res = partDist(w1, w2, w1len - 1, w2len - 1, SaveVal) +
                (w1.charAt(w1len - 1) == w2.charAt(w2len - 1) ? 0 : 1);
        int addLetter = partDist(w1, w2, w1len - 1, w2len, SaveVal) + 1;
        if (addLetter < res)
            res = addLetter;
        int deleteLetter = partDist(w1, w2, w1len, w2len - 1, SaveVal) + 1;
        if (deleteLetter < res)
            res = deleteLetter;
        SaveVal[w1len-1][w2len-1] = res;
        return res;
    }

    int Distance(String w1, String w2) {
        int simLetters = checkSim(w1, w2);
        //System.out.println(simLetters);
        if(simLetters > 0)  {
            //Reuse the old array used before
            int [][] tempVal = new int [w1.length()][w2.length()]; // w2.length()
            for(int i = 0; i < SaveVal.length; i++)  {

                for(int j=0; j < SaveVal[i].length; j++)  {
    ############### ERRROR HERE WHEN RUNNING PROGRAM ############
                    tempVal[i][j] = SaveVal[i][j];
                }
            }



            SaveVal = tempVal;
            return (partDist(w1, w2, w1.length(), w2.length(), SaveVal));
        } else {
            //Completly new word
            SaveVal = new int [w1.length()][w2.length()];
            return (partDist(w1, w2, w1.length(), w2.length(), SaveVal));
        }
    }
        /*SaveVal = new int [w1.length()][w2.length()];
        return (partDist(w1, w2, w1.length(), w2.length(), SaveVal));*/

    int checkSim(String w1, String w2)  {
        int counter = 0;
        if(savedWord == null || !savedWrongWord.equals(w1))  {
            return 0;
        }
        char[] char1 = savedWord.toCharArray();
        char[] char2 = w2.toCharArray();
        if(char1.length > char2.length) {
            for(int x = 0; x < char2.length; x++)  {
                if(char1[x] == char2[x])  {
                    counter++;
                }
            }
        }else {
            for(int x = 0; x < char1.length; x++)  {
                if(char1[x] == char2[x])  {
                    counter++;
                }
            }
        }
        return counter;
    }

    public ClosestWords(String w, List<String> wordList) {
        savedWrongWord = w;
        for (String s : wordList) {
            int dist = Distance(w, s);
            savedWord = s;
            if (dist < closestDistance || closestDistance == -1) {
                closestDistance = dist;
                closestWords = new LinkedList<String>();
                closestWords.add(s);
            }
            else if (dist == closestDistance)
                closestWords.add(s);
        }
    }

    int getMinDistance() {
        return closestDistance;
    }

    List<String> getClosestWords() {
        return closestWords;
    }
}

Answer 1

你遇到异常是因为 SaveVal 和 tmpVal 不使用相同的 w2。 在我的测试用例中:

        String w = "sa";
        List<String> arrays = new LinkedList<>();
        arrays.add("sdasfq");
        arrays.add("sad");
        ClosestWords words = new ClosestWords(w, arrays);
        System.out.println(words.getClosestWords());

SaveVal 是使用 w1="sa"和 w2="sdasfg"创建的。但是，当 w2 = "sad"时，不会再次创建 SaveVal。所以 SaveVal 是 int[2][7] 而 tmpVal 是 int[2][3]。

您只需使用 SaveVal 来加速方法 partDist 的执行。每次迭代 wordList 时都应该创建 SaveVal。我认为您不能重用不同 w2 之间的中间结果，例如“sdasfg”、“sad”。

因此，您可以删除字段 SaveVal，并在方法 Distance() 中将其声明为局部变量

    int Distance(String w1, String w2) {
        int SaveVal[][] = new int[w1.length()][w2.length()];
        return (partDist(w1, w2, w1.length(), w2.length(), SaveVal));
}

我无法理解方法 checkSim()。我认为这是多余的。 代码是:

import java.util.LinkedList;
import java.util.List;
import java.util.Arrays;

public class ClosestWords {
    LinkedList<String> closestWords = null;

//    int [][] SaveVal;
    int closestDistance = -1;
    static String savedWord;
    static String savedWrongWord;

    int partDist(String w1, String w2, int w1len, int w2len, int [][] SaveVal) {

        if (w1len == 0) {
            //return w2len;
            //SaveVal[0][w2len] = w2len;
            return w2len;
        }
        else if (w2len == 0) {
            //return w1len;
            //SaveVal[w1len][0] = w1len;
            return w1len;
        }
        else if(SaveVal[w1len-1][w2len-1] != 0) {
            return SaveVal[w1len-1][w2len-1];
        }

        int res = partDist(w1, w2, w1len - 1, w2len - 1, SaveVal) +
                (w1.charAt(w1len - 1) == w2.charAt(w2len - 1) ? 0 : 1);
        int addLetter = partDist(w1, w2, w1len - 1, w2len, SaveVal) + 1;
        if (addLetter < res)
            res = addLetter;
        int deleteLetter = partDist(w1, w2, w1len, w2len - 1, SaveVal) + 1;
        if (deleteLetter < res)
            res = deleteLetter;
        SaveVal[w1len-1][w2len-1] = res;
        return res;
    }

    int Distance(String w1, String w2) {
        int SaveVal[][] = new int[w1.length()][w2.length()];
        return (partDist(w1, w2, w1.length(), w2.length(), SaveVal));
    }


    public ClosestWords(String w, List<String> wordList) {
        savedWrongWord = w;
        for (String s : wordList) {
            int dist = Distance(w, s);
            savedWord = s;
            if (dist < closestDistance || closestDistance == -1) {
                closestDistance = dist;
                closestWords = new LinkedList<String>();
                closestWords.add(s);
            }
            else if (dist == closestDistance)
                closestWords.add(s);
        }
    }

    int getMinDistance() {
        return closestDistance;
    }

    List<String> getClosestWords() {
        return closestWords;
    }

    public static void main(String[] args) {
        String w = "sa";
        List<String> arrays = new LinkedList<>();
        arrays.add("sdasfq");
        arrays.add("sad");
        ClosestWords words = new ClosestWords(w, arrays);
        System.out.println(words.getClosestWords());
    }

}