javastring

Create strings with predefined conditions

Is there anything in java that does the opposite of regular expressions?

My task is: given a defined total length for a string and each position can only consist of predefined specific characters, generate all possible strings.

To give an example: I want to create all stings of length 3 where the positions are defined as

[ABC][123][XYZ]

This means that the first position can only be A, B or C, the second position one of the numbers 1 to 3 and so on. Valid strings would therefore be

A1X 
A1Y 
A1Z 
A2X 
A2Y 
A2Z 
...
... 
C3Z

For the length three I can of course use a nested loop. My problem is I don't know in advance how long the string has to be or how many valid characters each position has. Any ideas?

Code for length 3 and each position 3 possible chars:

public static void main(String[] args) {
    String[] first  = {"A", "B", "C"};
    String[] second = {"1", "2", "3"};
    String[] third  = {"X", "Y", "Z"};

    List<String> result = createStrings(first, second, third);

    result.forEach(System.out::println);
}

static List<String> createStrings(String[] ... strs) {
    String[] first  = strs[0];
    String[] second = strs[1];
    String[] third  = strs[2];

    List<String> result = new ArrayList<>();
    for (int i = 0; i < first.length; i++) {
        for (int j = 0; j < second.length; j++) {
            for (int k = 0; k < third.length; k++) {
                result.add(first[i] + second[j] + third[k]);
            }
        }
    }
    return result;
}

I need something flexible, which works for all inputs. Or a way to dynamically create a nested loop depending on strs.length which defines how many loops I need.

Solution

  • You can use recursion:

    import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        String[] first = { "A", "B", "C" };
        String[] second = { "1", "2", "3" };
        String[] third = { "X", "Y", "Z" };
        String[] fourth = { "K", "L", "M" };
        String[] fifth = { "7", "8", "9" };

        List<String> result = createStrings(first, second, third, fourth, fifth);

        result.forEach(System.out::println);
    }

    static List<String> createStrings(String[]... strs) {
        List<String> res = new ArrayList<>();
        getStrings(0, "", res, strs);
        return res;
    }

    static void getStrings(int level, String curr, List<String> res, String[]... strs) {
        if (level == strs.length) {
            res.add(curr);
            return;
        }

        for (String ch : strs[level]) {
            getStrings(level + 1, curr + ch, res, strs);
        }
    }
}

    Prints

    A1XK7
A1XK8
A1XK9
A1XL7
A1XL8
A1XL9
A1XM7
...

C3ZK9
C3ZL7
C3ZL8
C3ZL9
C3ZM7
C3ZM8
C3ZM9

    Tree level construction of a string:

    
                              ""
                            /  |  \
                          A    B    C
                         /|\  /|\  /|\
                       1 2 3 1 2 3 1 2 3
                      /|\ /|\ /|\ /|\ /|\
                     X Y Z X Y Z X Y Z X Y Z
                    /|\/|\/|\/|\/|\/|\/|\/|\
                   K L M K L M K L M K L M K L M
                  /|\/|\/|\/|\/|\/|\/|\/|\/|\/|\
                 ... ... ... ... ... ... ... ...

    Here are the recursion stacks:

    First Level (level = 0):

    Second Level (level = 1):

    Third Level (level = 2):

    Fourth Level (level = 3):

    Fifth Level (level = 4):

    ...

    Let's trace one path through the recursion stack: