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.
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.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments