All combinations of a string with special characters

Question

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?

• janos: Don't you need to generate *i* too from fin ?
• Aneesh K: Nope. The * character will only be occurring once and In a group
• janos: Alright then. In any case, I think this similar question, and @rolfl's answer may be enlightening: codereview.stackexchange.com/questions/83031/…

Answer 1

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