Time complexity analysis
Let's think about what this does.
for (char c : cArray) {
This says that for each character in the string (since cArray
is the character array view of the string), we iterate once. As you note, this is \$O(n)\$ where \$n\$ is the number of characters in the string.
Set<String> currResults = new HashSet<String>(results);
This is \$O(m)\$ where \$m\$ is the number of entries in the Set
. Note that that will change as you go.
String charToAdd = String.valueOf(c);
results.add(charToAdd);
This takes constant time.
for (String s : currResults) {
This takes \$O(m)\$ time again.
for (int i = 0; i < s.length() + 1; i++) {
This takes \$O(l)\$ time, where \$l\$ is the length of this string. Again, this will change over time.
String newWord = s.substring(0, i) + charToAdd + s.substring(i);
This takes \$O(l)\$ time, as it involves copying s
to a new string.
if (newWord.length() == str.length()) {
realRes.add(newWord);
}
else {
results.add(newWord);
}
This takes constant time.
We do \$n\$ iterations of the outer loop.
First iteration
\$n\$ is the number of characters in str
and will be throughout.
\$m\$ is 0. We haven't put any entries in the set yet.
\$l\$ doesn't exist. We never get to that section of code.
We end with one entry in results
and no entries in realRes
.
Second iteration
\$m\$ is 1.
\$l\$ is 1.
We end with three entries in results
and no entries in realRes
.
Third iteration
\$m\$ is 3. This is 2 + 1.
\$l\$ ranges from 2 to 1.
We end with nine entries in results
and no entries in realRes
.
Fourth iteration
\$m\$ is 9. This is 3 * 2 + 2 + 1.
\$l\$ ranges from 3 to 1.
We end with forty entries in results
and no entries in realRes
.
nth iteration
We end with \$n!\$ entries in realRes
. We add increasing numbers of strings to results
, equal to \$\sum\limits_{i=1}^{n-1} i!\$. Note that that is less than \$n!\$.
Note that this assumes that all the characters in the string are different. If some characters repeat, this will exaggerate the number of entries. Of course, for Big-O notation, that's fine. So we can say that overall this is still \$O(n!)\$.
Alternately styled code
public static Set<String> getPermutations(String str) {
Set<String> results = new HashSet<>();
Set<String> partials = new HashSet<>();
for (char c : str.toCharArray()) {
List<String> current = new ArrayList<>();
String charToAdd = String.valueOf(c);
for (String s : partials) {
for (int i = 0; i <= s.length(); i++) {
String newWord = s.substring(0, i) + charToAdd + s.substring(i);
if (newWord.length() == str.length()) {
results.add(newWord);
} else {
current.add(newWord);
}
}
}
partials.add(charToAdd);
partials.addAll(current);
}
return results;
}
I don't like the name results
for what you had. It's not results. It's partial permuations. So I changed it to partials
.
With the name results
available, I'd prefer that to realRes
.
I find it easier to read if we do the toCharArray
in the for
loop itself. That way I don't have to look around to find what cArray
is.
Rather than copy the entire set to another set on every iteration, I'd rather just copy the things that I'm adding. So I made a List
for that purpose. That (and moving the charToAdd
add
) allows us to loop directly over partials
rather than the new collection.
We can save a math operation if we say i <= s.length()
rather than i < s.length() + 1
. I also find it a bit clearer about what it is doing.
The Java standard is to do the fully cuddled else
. It's not a big deal if you do it the other way, but I changed that on my way through.