String permutations are the various possible strings made by the rearrangement of the characters in the original String.
For example, the permutations of car
are
car, cra, acr, arc, rac, rca
Write a recursive method getPermutations()
that returns all permutations of an input String
in an ArrayList
.
Define a helper method if needed. For the sake of simplicity, assume that all characters in the input String
are unique.
Examples:
getPermutations("") -> ArrayList -> []
getPermutations("c") -> ArrayList -> ["c"]
getPermutations("cat") -> ArrayList -> ["cat","cta","act","atc","tca","tac"]
*
String
one by one and recurse to find the permutation of the remaining String (you'll find the substring() method useful).The permutation of an empty String is an empty String. This could be the base condition.
To permute a set S, we can select the first character and permute the rest of the characters of the string to get a new list of all possible permutations. Now “push” the first character into each possible position.
For example, if our string is “abc
”, we would do the following:
1. Let first = “a”
and let remainder = “bc”
.
2. Let list = permute(bc) = {“bc”, “cd”}
.
3. Push “a
” into each location of “bc” (--> “abc”, “bac”, “bca”)
and “cb” (--> “acb”, “cab”, “cba”)
.
4. Return this new Arraylist.
public static ArrayList<String> getPermutations(String s) { }
C
Java
Python