原文:
给定一个字符串，按字典顺序打印一个字符串的所有组合。 例:
input: str = "abc"
output:
a
ab
abc
ac
acb
b
ba
bac
bc
bca
c
ca
cab
cb
cba
input: ed
output:
d
de
e
ed
方法:用地图计算字符串中所有字符的出现次数，然后用递归打印所有可能的组合。将元素及其计数存储在两个不同的数组中。使用三个数组，输入[]有字符的数组，计数[]有字符的数组，结果[]是一个临时数组，用于来生成所有的组合。使用和可以打印所有组合。 以下是上述办法的实施情况。
c
// c program to find all combinations
// of a string in lexicographical order
#include
using namespace std;
// function to print string
void printresult(char* result, int len)
{
for (int i = 0; i <= len; i )
cout << result[i];
cout << endl;
}
// method to found all combination
// of string it is based in tree
void stringcombination(char result[], char str[], int count[],
int level, int size, int length)
{
// return if level is equal size of string
if (level == size)
return;
for (int i = 0; i < length; i ) {
// if occurrence of char is 0 then
// skip the iteration of loop
if (count[i] == 0)
continue;
// decrease the char occurrence by 1
count[i]--;
// store the char in result
result[level] = str[i];
// print the string till level
printresult(result, level);
// call the function from level 1
stringcombination(result, str, count,
level 1, size, length);
// backtracking
count[i] ;
}
}
void combination(string str)
{
// declare the map for store
// each char with occurrence
map mp;
for (int i = 0; i < str.size(); i ) {
if (mp.find(str[i]) != mp.end())
mp[str[i]] = mp[str[i]] 1;
else
mp[str[i]] = 1;
}
// initialize the input array
// with all unique char
char* input = new char[mp.size()];
// initialize the count array with
// occurrence the unique char
int* count = new int[mp.size()];
// temporary char array for store the result
char* result = new char[str.size()];
map::iterator it = mp.begin();
int i = 0;
for (it; it != mp.end(); it ) {
// store the element of input array
input[i] = it->first;
// store the element of count array
count[i] = it->second;
i ;
}
// size of map(no of unique char)
int length = mp.size();
// size of original string
int size = str.size();
// call function for print string combination
stringcombination(result, input, count,
0, size, length);
}
// driver code
int main()
{
string str = "abc";
combination(str);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to find all combinations
// of a string in lexicographical order
import java.util.hashmap;
class gfg
{
// function to print string
static void printresult(char[] result,
int len)
{
for (int i = 0; i <= len; i )
system.out.print(result[i]);
system.out.println();
}
// method to found all combination
// of string it is based in tree
static void stringcombination(char[] result, char[] str,
int[] count, int level,
int size, int length)
{
// return if level is equal size of string
if (level == size)
return;
for (int i = 0; i < length; i )
{
// if occurrence of char is 0 then
// skip the iteration of loop
if (count[i] == 0)
continue;
// decrease the char occurrence by 1
count[i]--;
// store the char in result
result[level] = str[i];
// print the string till level
printresult(result, level);
// call the function from level 1
stringcombination(result, str, count,
level 1, size, length);
// backtracking
count[i] ;
}
}
static void combination(string str)
{
// declare the map for store
// each char with occurrence
hashmap mp = new hashmap<>();
for (int i = 0; i < str.length(); i )
mp.put(str.charat(i), mp.get(str.charat(i)) == null ? 1 :
mp.get(str.charat(i)) 1);
// initialize the input array
// with all unique char
char[] input = new char[mp.size()];
// initialize the count array with
// occurrence the unique char
int[] count = new int[mp.size()];
// temporary char array for store the result
char[] result = new char[str.length()];
int i = 0;
for (hashmap.entry entry : mp.entryset())
{
// store the element of input array
input[i] = entry.getkey();
// store the element of count array
count[i] = entry.getvalue();
i ;
}
// size of map(no of unique char)
int length = mp.size();
// size of original string
int size = str.length();
// call function for print string combination
stringcombination(result, input, count, 0,
size, length);
}
// driver code
public static void main (string[] args)
{
string str = "abc";
combination(str);
}
}
// this code is contributed by
// sanjeev2552
python 3
# python 3 program to find all combinations
# of a string in lexicographical order
from collections import defaultdict
# function to print string
def printresult(result, length):
for i in range(length 1):
print(result[i], end="")
print()
# method to found all combination
# of string it is based in tree
def stringcombination(result, st, count,
level, size, length):
# return if level is equal size of string
if (level == size):
return
for i in range(length):
# if occurrence of char is 0 then
# skip the iteration of loop
if (count[i] == 0):
continue
# decrease the char occurrence by 1
count[i] -= 1
# store the char in result
result[level] = st[i]
# print the string till level
printresult(result, level)
# call the function from level 1
stringcombination(result, st, count,
level 1, size, length)
# backtracking
count[i] = 1
def combination(st):
# declare the map for store
# each char with occurrence
mp = defaultdict(int)
for i in range(len(st)):
if (st[i] in mp.keys()):
mp[st[i]] = mp[st[i]] 1
else:
mp[st[i]] = 1
# initialize the input array
# with all unique char
input = ['']*len(mp)
# initialize the count array with
# occurrence the unique char
count = [0] * len(mp)
# temporary char array for store the result
result = ['']*len(st)
i = 0
for key, value in mp.items():
# store the element of input array
input[i] = key
# store the element of count array
count[i] = value
i = 1
# size of map(no of unique char)
length = len(mp)
# size of original string
size = len(st)
# call function for print string combination
stringcombination(result, input, count,
0, size, length)
# driver code
if __name__ == "__main__":
st = "abc"
combination(st)
# this code is contributed by ukasp.
c
// c# program to find all combinations
// of a string in lexicographical order
using system;
using system.collections.generic;
class gfg
{
// function to print string
static void printresult(char[] result,
int len)
{
for (int i = 0; i <= len; i )
console.write(result[i]);
console.writeline();
}
// method to found all combination
// of string it is based in tree
static void stringcombination(char[] result, char[] str,
int[] count, int level,
int size, int length)
{
// return if level is equal size of string
if (level == size)
return;
for (int i = 0; i < length; i )
{
// if occurrence of char is 0 then
// skip the iteration of loop
if (count[i] == 0)
continue;
// decrease the char occurrence by 1
count[i]--;
// store the char in result
result[level] = str[i];
// print the string till level
printresult(result, level);
// call the function from level 1
stringcombination(result, str, count,
level 1, size, length);
// backtracking
count[i] ;
}
}
static void combination(string str)
{
int i;
// declare the map for store
// each char with occurrence
dictionary mp = new dictionary();
for (i= 0; i < str.length; i )
if(mp.containskey(str[i]))
mp[str[i]] = mp[str[i]] 1;
else
mp.add(str[i], 1);
// initialize the input array
// with all unique char
char[] input = new char[mp.count];
// initialize the count array with
// occurrence the unique char
int[] count = new int[mp.count];
// temporary char array for store the result
char[] result = new char[str.length];
i = 0;
foreach(keyvaluepair entry in mp)
{
// store the element of input array
input[i] = entry.key;
// store the element of count array
count[i] = entry.value;
i ;
}
// size of map(no of unique char)
int length = mp.count;
// size of original string
int size = str.length;
// call function for print string combination
stringcombination(result, input, count, 0,
size, length);
}
// driver code
public static void main(string[] args)
{
string str = "abc";
combination(str);
}
}
// this code is contributed by rajput-ji
java 描述语言
output:
a
ab
abc
ac
acb
b
ba
bac
bc
bca
c
ca
cab
cb
cba
时间复杂度: o( )其中 n 是字符串的大小。 辅助空间: o(n)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
