3
\$\begingroup\$

I have written a function which generates combinations of string by replacing 1 or more characters by the symbol "*".

The code is as follows:

/**
        this following code is responsible to generate all possible combiantions of letters from a 
        word with *
        for eg. word = "fin", 
        wordSet --> {fin, fi*, f**, f*n, **n, ***,*in}

*/
public static void generateCombinations(Set<String> words){

        Set<String> wordSet = new HashSet<>();


        for (String word : words){

            StringBuilder asterisk = new StringBuilder("*");

            while (asterisk.length() != word.length()){

                int startIndex = 0;
                while (startIndex + asterisk.length() < word.length()) {
                    String tempWord = word.substring(0, startIndex)
                            + asterisk.toString()
                            + word.substring(startIndex +  asterisk.length());
                    wordSet.add(tempWord);
                    startIndex ++;
                }
                wordSet.add(word.substring(0, Math.abs(startIndex - asterisk.length()+1 ))+ asterisk.toString() );

                //loop condition incrementor
                asterisk.append("*");
            }
            //all *'s
            wordSet.add(asterisk.toString());
            //no *
            wordSet.add(word);
        }
        //System.out.println(wordSet);

    }

However, I think this is a highly inefficient code as I need to do the same operation for all the words in the given Set of words(Set<String> words).

Is there any faster way to generate the same result? Any improvements in the current function to enhance speed and readability?

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Don't you need to generate *i* too from fin ? \$\endgroup\$ – janos Mar 10 '15 at 15:05
  • \$\begingroup\$ Nope. The * character will only be occurring once and In a group \$\endgroup\$ – Aneesh K Mar 10 '15 at 15:56
  • 1
    \$\begingroup\$ Alright then. In any case, I think this similar question, and @rolfl's answer may be enlightening: codereview.stackexchange.com/questions/83031/… \$\endgroup\$ – janos Mar 10 '15 at 15:57
2
\$\begingroup\$

Well, you can simply find out where the * can be, e.g.:

___, __*, _**, _*_, **_, ***,*__

and then replace:

fin, fi*, f**, f*n, **n, ***,*in

Code:

public static String[] possibleCombinations(String s) {
    int length = s.length();
    char[][] strings = new char[length * (length + 1) / 2][length];
    for (int i = 0; i < strings.length; i++) {
        strings[i] = s.toCharArray();
    }
    strings[0][0] = '*';
    for (int i = 0, j = 0, counter = 0; i < length; i++, counter += length - i + 1, j = i) {
        for (; j < length; j++) {
            for (int k = j; k < length; k++) {
                strings[counter + k - i][j] = '*';
            }
        }
    }
    String[] result = new String[strings.length + 1];
    result[0] = s;
    for (int i = 0; i < strings.length; i++) {
        result[i + 1] = new String(strings[i]);
    }
    return result;
}

It's fairly fast:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
*aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
**aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
***aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
...
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa***
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa*a
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa**
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa*
length: 50
Time taken: 1064956 nanoseconds

Length: 500
Time taken: 733033361 nanoseconds
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.