How can I have out parameters in Java?

Question

My objective is to recursively iterate a R-way trie, and find the longest common prefix that prefixes at least two strings, and how many strings it concerns. I have written various methods to solve this, but I'm not satisfied with the technical aspects of them.

Example input:

figure, fight, finger, english, entail

output:

Longest prefix: fig

Number of Strings: 2

Here's how I implemented solutions:

The nodes have a timesUsed attribute, that increments every time that node is visited when inserting new strings to the trie.

    public void allPrefixes() {
        ArrayList<String> list = new ArrayList<>();
        ArrayList<Integer> timesUsed = new ArrayList<>();

        allPrefixesUtil(list, timesUsed, root, "");

        int longestPrefixIndex = getLongestIndex(list);

        System.out.println("Longest common prefix: " + list.get(longestPrefixIndex));
        System.out.println("Number of strings: " + timesUsed.get(longestPrefixIndex));
    }

    public void allPrefixesUtil(ArrayList<String> list, ArrayList<Integer> timesUsed, Node x, String s) {
        for (int i = 0; i < x.next.length; i++) {
            if (x.next[i] != null && x.next[i].timesUsed >= 2) {
                list.add(s + (char) (i + 'a'));
                timesUsed.add(x.next[i].timesUsed);
                allPrefixesUtil(list, timesUsed, x.next[i], s + (char) (i + 'a'));
            }
        }
    }

The code here adds every prefix that occurs more than once, so the list looks like this: e, en, f, fi, fig. I then find the longest among these strings and print it along with the corresponding timesUsed index. This solution uses a lot of space, so I decided to try something else.

Next, I tried this:

    public void allPrefixes2() {
        String longest = "";
        int timesUsed = 0;

        allPrefixesUtil2(longest, timesUsed, root, "");

        System.out.println("Longest common prefix: " + longest);
        System.out.println("Number of strings: " + timesUsed);
    }

    public void allPrefixesUtil2(String longest, int timesUsed, Node x, String s) {
        for (int i = 0; i < x.next.length; i++) {
            Node nextNode = x.next[i];
            if (nextNode != null && nextNode.timesUsed >= 2) {
                String str = s + (char) (i + 'a');
                if (str.length() > longest.length()) {
                    longest = new String(str);
                    timesUsed = nextNode.timesUsed;
                }
                allPrefixesUtil2(longest, timesUsed, nextNode, str);
            }
        }
    }

Instead of adding every prefix to a list and calculating the longest, I decided to reassign the longest string whenever a longer string is encountered. This obviously did not work as Java is pass-by-value. To work around this, I changed the string and integer into single element arrays.

    public void allPrefixes2() {
        String[] longest = { "" };
        int[] timesUsed = { 0 };

        allPrefixesUtil2(longest, timesUsed, root, "");

        System.out.println("Longest common prefix: " + longest[0]);
        System.out.println("Number of strings: " + timesUsed[0]);
    }

This works, but... I'm not sure if it's clever or stupid. I could not find a better way if I want to use temporary variables.

I did however lastly make it so that the trie has a longest and a timesUsed attribute, and just directly pass those into the method. It worked but this time, adding these attributes to the trie did not sit right with me. It's odd that a generic tree would have those attributes.

So what should I do? Which is the best among all these options? What's better than all three? I'm not sure which is the best conventional and practical method here, except that the first one is not space efficient.

Answer 1

The problem you are having is not really because Java is "pass-by-value".

The problem you are encountering is that Strings are immutable and when you assign a new value to the local parameter named longest it just disappears as soon as it goes out of scope.

You can get around this relatively easily by passing an array of length one instead.

 public void allPrefixes2() {
        String[] longest = {""};
        int timesUsed = 0;

        allPrefixesUtil2(longest, timesUsed, root, "");

        System.out.println("Longest common prefix: " + longest);
        System.out.println("Number of strings: " + timesUsed);
    }

    public void allPrefixesUtil2(String[] longest, int timesUsed, Node x, String s) {
        for (int i = 0; i < x.next.length; i++) {
            Node nextNode = x.next[i];
            if (nextNode != null && nextNode.timesUsed >= 2) {
                String str = s + (char) (i + 'a');
                if (str.length() > longest[0].length()) {
                    longest[0] = new String(str);
                    timesUsed = nextNode.timesUsed;
                }
                allPrefixesUtil2(longest, timesUsed, nextNode, str);
            }
        }
    }