优化单词距离计算时复制矩阵触发ArrayIndexOutOfBoundsException异常

看起来你在实现基于编辑距离的单词匹配程序时，遇到了数组越界的问题，我来帮你拆解一下问题根源和修复方案。

直接报错原因：矩阵维度不匹配导致越界 #

在Distance方法中，当你尝试复用之前的SaveVal矩阵到新的tempVal时，没有考虑两个矩阵的维度差异：

// 问题代码
for(int i = 0; i < SaveVal.length; i++) {
    for(int j=0; j < SaveVal[i].length; j++) {
        tempVal[i][j] = SaveVal[i][j]; // 这里会触发越界
    }
}

举个例子：假设上一个字典单词长度是5，当前处理的单词长度是3，那么SaveVal的列数是5，而新创建的tempVal列数是3。当j循环到3时，tempVal[i][3]是不存在的索引，直接触发ArrayIndexOutOfBoundsException。

深层逻辑问题：复用条件判断不准确 #

你的checkSim方法只是判断了当前字典单词和上一个单词的前缀相似字符数，但相似字符数>0并不代表两个单词的长度适合复用整个矩阵。即使前缀有部分相同，只要两个单词长度不同，矩阵的列数就不一样，直接全量复制必然会越界。

另外，使用静态变量SaveVal、savedWord、savedWrongWord也存在风险——如果创建多个ClosestWords实例，静态变量的状态会互相干扰，导致逻辑混乱。

修复方案 #

1. 先解决数组越界问题：只复制矩阵的重叠部分 #

修改Distance方法中的复制逻辑，只复制两个矩阵共同拥有的行列范围：

if(simLetters > 0) {
    int [][] tempVal = new int [w1.length()][w2.length()];
    // 取两个矩阵行和列的最小值，避免越界
    int minRows = Math.min(SaveVal.length, tempVal.length);
    int minCols = Math.min(SaveVal[0].length, tempVal[0].length);
    for(int i = 0; i < minRows; i++) {
        for(int j=0; j < minCols; j++) {
            tempVal[i][j] = SaveVal[i][j];
        }
    }
    SaveVal = tempVal;
    return partDist(w1, w2, w1.length(), w2.length(), SaveVal);
}

这样可以避免访问不存在的索引，先解决报错问题。

2. 优化复用逻辑：准确判断可复用的矩阵范围 #

你的复用思路是对的——复用已计算的编辑距离结果来提升性能，但需要更精准的判断：只有当当前字典单词和上一个单词的前缀完全匹配到某个长度时，对应的矩阵部分才可以复用。比如，上一个单词是"apple"，当前是"app"，那么可以复用tempVal[i][0-2]的结果（因为前3个字符相同）。

可以修改checkSim方法，返回两个单词的最长公共前缀长度，而不是相似字符数：

int getCommonPrefixLength(String sPrev, String sCurr) {
    if(sPrev == null) return 0;
    int minLen = Math.min(sPrev.length(), sCurr.length());
    for(int i=0; i<minLen; i++) {
        if(sPrev.charAt(i) != sCurr.charAt(i)) {
            return i;
        }
    }
    return minLen;
}

然后在Distance方法中，只复制公共前缀对应的矩阵列：

int commonPrefixLen = getCommonPrefixLength(savedWord, w2);
if(commonPrefixLen > 0) {
    int [][] tempVal = new int [w1.length()][w2.length()];
    // 只复制公共前缀长度内的列
    for(int i = 0; i < w1.length(); i++) {
        for(int j=0; j < commonPrefixLen; j++) {
            tempVal[i][j] = SaveVal[i][j];
        }
    }
    SaveVal = tempVal;
    return partDist(w1, w2, w1.length(), w2.length(), SaveVal);
}

这样既保证了复用有效计算结果，又不会出现维度不匹配的问题。

3. 替换静态变量为实例变量 #

把SaveVal、savedWord、savedWrongWord从静态变量改为实例变量，避免多实例之间的状态干扰：

public class ClosestWords {
    LinkedList<String> closestWords = null;
    int [][] SaveVal; // 去掉static修饰符
    int closestDistance = -1;
    String savedWord; // 去掉static修饰符
    String savedWrongWord; // 去掉static修饰符

    // 其余方法保持不变...
}

额外优化建议 #

编辑距离计算的递归实现虽然直观，但性能不算最优，你可以考虑改成迭代版的动态规划，结合滚动数组优化空间复杂度（从O(mn)降到O(min(m,n))），同时更便于控制矩阵的复用逻辑。

内容的提问来源于stack exchange，提问作者Japaleno