Java 实现编辑距离算法（无二维数组）

以下是一个基于滚动数组的编辑距离算法的 Java 实现，该实现可以有效地计算两个字符串之间的编辑距离，同时避免了使用二维数组，降低了空间复杂度。

public static int editDistance(String s1, String s2) {
    if (s1 == null || s2 == null) {
        return -1;
    }
    int len1 = s1.length();
    int len2 = s2.length();
    if (len1 == 0) {
        return len2;
    }
    if (len2 == 0) {
        return len1;
    }
    if (len1 < len2) {
        String tmp = s1;
        s1 = s2;
        s2 = tmp;
        len1 = s1.length();
        len2 = s2.length();
    }
    int[] dp = new int[len2 + 1];
    for (int j = 0; j <= len2; j++) {
        dp[j] = j;
    }
    for (int i = 1; i <= len1; i++) {
        int pre = dp[0];
        dp[0] = i;
        for (int j = 1; j <= len2; j++) {
            int tmp = dp[j];
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                dp[j] = pre;
            } else {
                dp[j] = Math.min(pre, Math.min(dp[j - 1], dp[j])) + 1;
            }
            pre = tmp;
        }
    }
    return dp[len2];
}

该实现中，我们利用了滚动数组的思想，只使用了一个一维数组 dp 来存储上一行的结果。这样可以节省空间，使得算法的空间复杂度降低到 O(min(len1, len2))。同时，我们使用了一个变量 pre 来保存上一列的结果，避免使用二维数组。算法的时间复杂度为 O(len1 * len2)。

通过这种优化，我们可以有效地计算字符串之间的编辑距离，同时减少了内存占用，提高了算法的效率。