Replace substring with a regex combination

Question

Since I'm not that familiar with java, I don't know if there's a library somewhere that can do this thing. If not, does anybody have any ideas how can this be accomplished?

For instance I have a string "foo" and I want to change the letter f with "f" and "a" so that the function returns a list of strings with values "foo" and "aoo".

How to deal with it when there's more of the same letters? "ffoo" into "ffoo", "afoo", "faoo", "aaoo".

A better explanation: (("a",("a","b)),("c",("c","d"))) Above is a group of characters that need to be replaced with a character from the other element. "a" is to be replaced with "a" and with "b". "c" is to be replaced with "c" and "d".

If I have a string "ac", the resulting combinations I need are: "ac" "bc" "ad" "bd"

If the string is "IaJaKc", the resulting combinations are: "IaJaKc" "IbJaKc" "IaJbKc" "IbJbKc" "IaJaKd" "IbJaKd" "IaJbKd" "IbJbKd"

The number of combinations can be calculated like this: (replacements_of_a^letter_amount_a)*(replacements_of_c^letter_amount_c) first case: 2^1*2^1 = 4 second case: 2^2*2^1 = 8

If, say, the group is (("a",("a","b)),("c",("c","d","e"))), and the string is "aac", the number of combinations is: 2^2*3^1 = 12

Answer 1

Here is the code for your example with foo and aoo

public List<String> doSmthTricky (String str) {
    return Arrays.asList("foo".replaceAll("(^.)(.*)", "$1$2 a$2").split(" "));
}

For the input "foo" this method returns a list with 2 strings "foo" and "aoo".

It works only if there is no whitespaces in your input string ("foo" in your example). Otherwise it's a bit more complicated.

How to deal with it when there's more of the same letters? "ffoo" into "ffoo", "afoo", "faoo", "aaoo".

I doubt that regular expressions could help here, you want to generate strings based on initial string, it's not a task for regexp.

UPD: I've created a recursive function (actually it's half-recursive half-iterative) which generates strings based on the template string by replacing its first characters with characters from a specified set:

public static List<String> generatePermutations (String template, String chars, int depth, List<String> result) {
    if (depth <= 0) {
        result.add (template);
        return result;
    }
    for (int i = 0; i < chars.length(); i++) {
        String newTemplate = template.substring(0, depth - 1) + chars.charAt(i) + template.substring(depth);
        generatePermutations(newTemplate, chars, depth - 1, result);
    }
    generatePermutations(template, chars, depth - 1, result);
    return result;
}

Parameter @depth means how many characters from the beginning of string should be replaced. Number of permutations (chars.size() + 1) ^ depth.

Tests:

System.out.println(generatePermutations("ffoo", "a", 2, new LinkedList<String>()));

Output: [aaoo, faoo, afoo, ffoo]

--
System.out.println(generatePermutations("ffoo", "ab", 3, new LinkedList<String>()));

Output: [aaao, baao, faao, abao, bbao, fbao, afao, bfao, ffao, aabo, babo, fabo, abbo, bbbo, fbbo, afbo, bfbo, ffbo, aaoo, baoo, faoo, aboo, bboo, fboo, afoo, bfoo, ffoo]

Answer 2

I'm not sure what you need. Please specify source and the result you expect. Anyway, you should use standard java classes for that purpose: java.util.regex.Pattern, java.util.regex.Matcher. If you need to deal with the repeating letters in the beginning, then there is two ways, use symbol "^" - which means beginning of the line, or for the same purpose you can use "\w" shortcut, which means beginning of the word. In more sophisticated cases, please take a look at "lookbehind" expressions. There are more than complete descriptions of these techniques you can find in java doc for java.util.regex and if it's not enough look at www.regular-expressions.info good luck.

Answer 3

Here it is:

public static void returnVariants(String input){
        List<String> output = new ArrayList<String>();
        StringBuffer word = new StringBuffer(input);
        output.add(input);

        String letters = "ac";
        int lettersLength = letters.length();
        int wordLength = word.length();
        String replacement = "";

        for (int i = 0; i < lettersLength; i++) {
            for (int j = 0; j < wordLength; j++) {
                if(word.charAt(j)==letters.charAt(i)){
                    if (word.charAt(j)=='a'){
                        replacement = "ab";
                    }else if (word.charAt(j)=='c'){
                        replacement = "cd";
                    }
                    List<String> tempList = new ArrayList<String>();
                    for (int k = 0; k < replacement.length(); k++) {
                        for (String variant : output){
                            StringBuffer tempBuffer = new StringBuffer(variant);
                            String combination = tempBuffer.replace(j, j+1, replacement.substring(k, k+1)).toString();
                            tempList.add(combination);
                        }
                    }
                    output.addAll(tempList);
                    if (j==0){
                        output.remove(0);
                    }
                }
            }
        }
        Set<String> uniqueCombinations = new HashSet(output);
        System.out.println(uniqueCombinations);
    }

If input is "ac", the combinations returned are "ac", "bc", "ad", "bd". If it can be optimized further, any additional help is welcome and appreciated.