CODEWITHSUNDEEP
javaalgorithmrecursiondynamic-programminglcs
daniel
daniel

Reputation: 221

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

I have this code to find "All Longest Common Sequences" and their length.

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));
    }
}

The problem with this code is that I have to use lcsList as a "global" variable.

How can I avoid accessing outside variables in allPaths?

I can probably do something like this, but it does not look right:

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();
}

What if i have 100 functions in this class and they all have this outside variable? It seems like a bad practice.

Upvotes: 1

Views: 140

Answers (1)

Devstr
Devstr

Reputation: 4641

You can just pass a mutable container as an accumulator parameter like this: note the new paths parameter.

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));
}

The results I get contain duplicates ([abbae, abace, abace, abace]) so you might want to use Set instead:

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

P.S. I'd also note that using string concatenation for constructing a path is not very effective, because a new String object is created every time (as Strings are immutable). You should rather use StringBuilder and its insert operation.

Upvotes: 1

Related Questions