java

Question

我有这段代码可以找到 "All Longest Common Sequences" 及其长度。

public class LCS {
    static Set<String> lcsList = new HashSet<>();

    public static int[][] twoStringMatrix(String a, String b) {
        int arr[][] = new int[a.length() + 1][b.length() + 1];

        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j < arr[0].length; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    arr[i][j] = arr[i - 1][j - 1] + 1;
                } else {
                    arr[i][j] = Math.max(arr[i][j - 1], arr[i - 1][j]);
                }
            }
        }
        return arr;
    }

    public static int lengthLcs(int[][] twoStringMatrix) {
        return twoStringMatrix[twoStringMatrix.length - 1][twoStringMatrix[0].length - 1];
    }

    public static void allPaths(String a, String b, int i, int j, String s, int arr[][]) {
        if (i > 0 && j > 0) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                allPaths(a, b, i - 1, j - 1, a.charAt(i - 1) + s, arr);
            } else if (arr[i][j - 1] == arr[i - 1][j]) {
                allPaths(a, b, i, j - 1, s, arr);
                allPaths(a, b, i - 1, j, s, arr);
            } else if (arr[i][j - 1] > arr[i - 1][j]) {
                allPaths(a, b, i, j - 1, s, arr);
            } else if (arr[i][j - 1] < arr[i - 1][j]) {
                allPaths(a, b, i - 1, j, s, arr);
            }
        } else {
            lcsList.add(s);
        }
    }

    public static void main(String[] args) {
        String b = "abbaecde";
        String a = "abacbae";

        System.out.println("length = " + twoStringMatrix(a, b).length);
        System.out.println("length = " + twoStringMatrix(a, b)[0].length);
        allPaths(a, b, a.length(), b.length(), "", twoStringMatrix(a, b));
        System.out.println((lcsList));
    }
}

此代码的问题是我必须使用 lcsList 作为 "global" 变量。

如何避免在 allPaths 中访问外部变量？

我可能会做这样的事情，但它看起来不对：

public static void getAll(String a, String b, int i, int j, String s, int arr[][]){
    allPaths(a, b, a.length(), b.length(), "", twoStringMatrix(a, b));
    System.out.println(lcsList);
    lcsList.clear();
}

如果我在这个 class 中有 100 个函数并且它们都有这个外部变量怎么办？这似乎是一种不好的做法。

Answer 1

您可以像这样将可变容器作为累加器参数传递：请注意新的 paths 参数。

public static void allPaths(String a, String b, int i, int j, String s, int[][] arr, List<String> paths) {
    if (i > 0 && j > 0) {
        if (a.charAt(i - 1) == b.charAt(j - 1)) {
            allPaths(a, b, i - 1, j - 1, a.charAt(i - 1) + s, arr, paths);
        } else if (arr[i][j - 1] == arr[i - 1][j]) {
            allPaths(a, b, i, j - 1, s, arr, paths);
            allPaths(a, b, i - 1, j, s, arr, paths);
        } else if (arr[i][j - 1] > arr[i - 1][j]) {
            allPaths(a, b, i, j - 1, s, arr, paths);
        } else if (arr[i][j - 1] < arr[i - 1][j]) {
            allPaths(a, b, i - 1, j, s, arr, paths);
        }
    } else {
        paths.add(s);
    }
}

public static void main(String[] args) {
    String b = "abbaecde";
    String a = "abacbae";

    final List<String> paths = new ArrayList<>();
    allPaths(a, b, a.length(), b.length(), "", twoStringMatrix(a, b), paths);
    System.out.println((paths));
}

我得到的结果包含重复项 ([abbae, abace, abace, abace])，因此您可能想改用 Set：

 final Set<String> paths = new HashSet<>();

P.S。我还注意到使用字符串连接来构造路径不是很有效，因为每次都会创建一个新的 String 对象（因为 String 是不可变的）。您应该使用 StringBuilder 及其 insert 操作。

java - 如何避免全局外部变量作为递归函数的输出

java - how to avoid global external variable as output in recursive function

algorithm

recursion

dynamic-programming

lcs