To understand this solution first understand the concept of recursion.
So here lets assume a given string S represented by S1,S2,S2....,Sn.
To permute String S ,we can select the first character S1,permute the remainder of string to get a new list.Then with a new list we can push S1 into each possible positions.
import java.util.ArrayList;
import java.util.List;
/**
*
*/
/**
* @author Dixit
*
*/
public class StringPermutation {
/**
* @param args
*/
public static void main(String[] args) {
List<String> listOfAllPermutatuons=getPerms("abc");
for(String s:listOfAllPermutatuons)
{
System.out.println(s);
}
}
public static ArrayList<String> getPerms(String s) {
ArrayList<String> permutations = new ArrayList<String>();
if (s == null) {
return null;
} else if (s.length() == 0) {
permutations.add("");
return permutations;
}
char first = s.charAt(0); // get the first character
String remainder = s.substring(1); // remove the first character
ArrayList<String> words = getPerms(remainder);
for (String word : words) {
for (int j = 0; j <= word.length(); j++) {
permutations.add(insertCharAt(word, first, j));
}
}
return permutations;
}
public static String insertCharAt(String word, char c, int i) {
String start = word.substring(0, i);
String end = word.substring(i);
return start + c + end;
}
}
Output
abc
bac
bca
acb
cab
cba
NOTE:- To understand this solution clearly,try to put a debug point and go through each line.
Enjoy Programming
No comments:
Post a Comment