java implements a full array of strings
- 2021-01-19 22:16:41
- OfStack
The full arrangement of the string, the specific content is as follows
Enter a string and print out all the permutations of the characters in the string in lexicographic order. For example the input string abc, then print out by character a, b, c abc can arrange out of all the string acb, bac, bca, cab and cba. Please output the results in alphabetical order.
Using the recursive idea:
Divide the string that needs to be fully arranged into two parts:
(1) The first character of the string;
(2) All characters after the first character;
Find all possible characters in the first position; Swap the first character with the following character once;
Fixed the first character, the first character of all the characters after the full arrangement. All characters after the first character can be divided into two parts;
java code:
import java.util.ArrayList;
import java.util.TreeSet;
public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList<String> res = new ArrayList<String>();
if(str==null||str.length()==0)
{
return res;
}
char[] charArray = str.toCharArray();
// The output is in input dictionary order
TreeSet<String> tempRes = new TreeSet<String>();
PermutationCore(charArray,tempRes,0);
res.addAll(tempRes);
return res;
}
private void PermutationCore( char[] charArray,TreeSet<String> tempRes,int loc)
{
if(charArray==null || charArray.length==0 || loc<0 || loc>charArray.length-1)
{
return ;
}
if(loc==charArray.length-1)
{
tempRes.add(String.valueOf(charArray));// Recursion exits
}
else
{
for(int i=loc;i<charArray.length;i++)
{
swap(charArray,i,loc);// Will be the first 1 Is exchanged with the following characters
PermutationCore(charArray,tempRes,loc+1);// Perform a full array of all subsequent characters
swap(charArray,i,loc);// Swap the previously swapped characters back so that the first 1 Is exchanged with other characters
}
}
}
private void swap(char[] charArray,int i,int j)
{
char temp = charArray[i];
charArray[i] = charArray[j];
charArray[j] = temp;
}
}