Problem
Print all the permutations of the given Java String. Permutation means the number of arranging the characters of String in all possible sequences. The number of permutations of the given string is factorial of n (n!), where n is the number of characters in the String.
Example – For ABC input, permutations are ABC, ACB, BAC, BCA, CAB, CBA. Count – 3! = 1 x 2 x 3 = 6.
Solution
- Uses recursion (backtracking method).
- Time complexity – O(n*n!). n for printing the output and n! for recursion.
package com.computepatterns.problemsolving.string;
/**
* Permutation of a string.
* Algorithm uses recursion.
* Number of permuted items - Factorial of (length of string).
* Example - Permutations of ABC is [ABC, ACB, BAC, BCA, CAB, CBA]
* Time complexity - O(n*n!) - n for printing the output and n! for the recursion.
*/
public class Permutation {
public void permute(String input){
permute("", input);
}
private void permute(String prefix, String suffix){
if(1 == suffix.length()){
System.out.println(prefix + suffix);
}else {
for (int i = 0; i < suffix.length(); i++) {
permute(prefix + suffix.charAt(i), suffix.substring(0,i) + suffix.substring(i+1, suffix.length()));
}
}
}
public static void main(String[] args) {
new Permutation().permute("ABC");
}
}