java implements the string permutation and combination problem
- 2021-01-22 05:06:34
- OfStack
This paper introduces java to achieve string perturbation and combination problems, for your reference, the specific content is as follows
import java.util.ArrayList;
import java.util.Collections;
/**
* The input 1 A string , Prints all permutations of the characters in the string in lexicographical order. For example, the input string abc, Then print out by character a,b,c All the strings that can be sorted abc,acb,bac,
* bca,cab and cba .
*
* @author pomay
*
*/
public class Solution_stringarrange
{
public ArrayList<String> Permutation(String str)
{
if (str == null)
return null;
ArrayList<String> list = new ArrayList<String>();
char[] pStr = str.toCharArray();
Permutation(pStr, 0, list);
Collections.sort(list);
return list;
}
static void Permutation(char[] str, int i, ArrayList<String> list)
{
// If it is empty
if (str == null)
return;
// if i It goes to the end 1 A character
if (i == str.length - 1)
{
if (list.contains(String.valueOf(str)))
return;
list.add(String.valueOf(str));
} else
{
// i Point to the fourth string in which we are currently sorting 1 A character
for (int j = i; j < str.length; j++)
{
// The first of the strings to be sorted 1 Is exchanged with all subsequent characters
char temp = str[j];
str[j] = str[i];
str[i] = temp;
// After exchange of i The following strings are recursively sorted
Permutation(str, i + 1, list);
// every 1 After the end of the round change back to the next 1 Wheel arrangement operation
temp = str[j];
str[j] = str[i];
str[i] = temp;
}
}
}
public static void main(String[] args)
{
String str = "aab";
Solution_stringarrange changestring = new Solution_stringarrange();
ArrayList<String> list = changestring.Permutation(str);
for (int i = 0; i < list.size(); i++)
{
System.out.print(list.get(i) + " ");
}
}
}
Combination:
Either select the first character in the string of length n, then select m-1 character in the remaining string of length n-1
Either the first character in the string of length n is not selected, then m characters are selected in the remaining string of length n-1
import java.util.ArrayList;
import java.util.List;
/**
* The input 1 A string , Prints all combinations of characters in the string lexicographically. For example, the input string abc, Then print out by character a,b,c All the strings that can be sorted a,b,c,ab,ac,bc
* ,abc . o n The composition length of characters is m Combinatorial problem of
*
* @author pomay
*
*/
public class Solution_stringcombination
{
// Find the combination of all characters in a string abc>a,b,c,ab,ac,bc,abc
public static void perm(String s)
{
List<String> result = new ArrayList<String>();
// from 1 A start
for (int i = 1; i <= s.length(); i++)
{
combination(s, i, result);
}
}
// From a string s Select the m A character
public static void combination(String s, int m, List<String> result)
{
// if m==0 , the recursion ends. Output the current result
if (m == 0)
{
for (int i = 0; i < result.size(); i++)
{
System.out.print(result.get(i));
}
System.out.print(" , ");
return;
}
if (s.length() != 0)
{
// Select the current element
result.add(s.charAt(0) + "");
// substring Use, extract from 1 Start to n Terminated string
combination(s.substring(1, s.length()), m - 1, result);
result.remove(result.size() - 1);
// The current element is not selected
combination(s.substring(1, s.length()), m, result);
}
}
public static void main(String[] args)
{
String str = "abc";
perm(str);
}
}