Java Duel: May 2012

This is one question you will come across in one or the other java interviews. Though it sounds very difficult when you hear it for the first time, but actually this can be achieved quite easily if you think about it a little in terms of recursion.

Lets take a simple example of a string "ABC" to understand and see how this can be done.

Here, we will see how to approach the problem and try to reach a solution .

Solution:

We start the solution with 2 Strings one given as input and other empty which we call as the output. Then we start creating all the permutations of the string iteratively and recursively.

What need to do is take a character out from the given string, populate it in the output string. All we need to do now is to do this step again with these updated string. Here is the Java code snippet to do the same.

 public void permute (String output, String input){
  String temp = null;
  if(input.length() > 1){
   for(int i = 0; i < input.length(); i++){
    temp = removeCharacter(input, input.charAt(i));
    permute(output+input.charAt(i), temp);
   }
  } else {
   System.out.println(output+input);
  }
  
 }
 
 public String removeCharacter(String input, char c){
  StringBuilder temp = new StringBuilder(input);
  int index = input.indexOf(c);
  temp.replace(index, index+1, "");
  return temp.toString();
 }

For generating all permutations of a String "ABCD", we need to a call to the method permute like

1	permute("", "ABCD");

Below is the diagram which depicts how each string varies after each iteration and each recursive call. Each level in the tree represents represents a recursive call whereas siblings in the tree represents the iteration.

This code will work only if all the characters in the input string are unique, but will generate some repeated permutations if some or all of the characters are repeated.

Now the question arises, how to handle the scenario where characters are repeated? What you can do is instead of displaying a permutation as and when you get it, you can store it in HashSet. This will eliminate all the duplicates. At the end you can display the entire content of the set. Though this approach works there are memory implication if your input string is really large. To handle those scenarios the algorithm in itself needs to be enhanced to take care of duplicates strings, without using extra memory to the extent of storing all the strings created.

Java Duel

Saturday, May 05, 2012

How To : All Permutations of a String

About Me