Is there a way to jump over specific strings on an iteration of a list of strings that is sorted lexicographically in Java?

Question

I have a list of strings lst that is sorted lexicographically and I want to iterate over the list in a way that each iteration, I jump to a string that starts with the following letter of the first letter of the previous string.

For example, lst=["aba, "ads", "aerfa", "ba", "bdf", "cg", "cqr", "deg"]

The iteration will be: "aba" --> "ba" --> "cg" --> "deq"

Answer 1

If your list is small, the easiest solution might be to get the first char (charAt(0)) and skip all subsequent elements until you find an element with a different first char, repeating that until the end of the list is reached.

Otherwise, assuming your list is random-access (for example ArrayList) you could probably do the following:

With two variables, one for the current index (initially 0), and one for the potential next char.

1. If current index >= size of the list, stop
2. Process the element at the current index, get its first char (chatAt(0)) increment it, cast it back to char and store it as next char (for non-ASCII text you might need more elaborate logic)
3. Create a sublist view with List.subList starting behind the current index and ending at the end of the list
4. Create a String from the next char (Character.toString(char)) and search it in the sublist from the previous step using Collections.binarySearch
   • If the result index >= 0 add it to current index (since it is relative to the sublist) and repeat all steps
   • Else calculate -(result + 1) (see binarySearch documentation) add it to current index (since it is relative to the sublist) and repeat all steps

(have not tested this implementation yet)

For a sorted String array you could probably get slightly better performance due to being able to use Arrays.binarySearch.

Maybe there are more efficient solutions to this though. Additionally, other data structures, such as NavigableSet or a Trie might be useful as well.

Answer 2

        List<String> list = Arrays.asList("aba", "ads", "aerfa", "ba", "bdf", "cg", "cqr", "deg");
        Iterator<String> iterator = list.iterator();
        char c = 0;
        while (iterator.hasNext()) {
            String val = iterator.next();
            if (val.charAt(0) <= c)
                continue;
            System.out.println(val);
            c = val.charAt(0);
        }