题目
打印一个字符串的全部排列
题解
每次递归都将后续字符与当前字符交换, 如第 i 次递归, 将 i 位置之后的字符分别与 i 处字符交换
若要去重使用集合即可
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| public class PrintPermutations {
public static void printPermutations(String str) {
char[] chars = str.toCharArray();
process(chars, 0);
}
public static void process(char[] chars, int i) {
if (i == chars.length) {
System.out.println(String.valueOf(chars));
}
for (int j = i; j < chars.length; j++) {
swap(chars, i, j);
process(chars, i + 1);
}
}
public static void swap(char[] chars, int i, int j) {
char tmp = chars[i];
chars[i] = chars[j];
chars[j] = tmp;
}
}
|
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
| def print_permutations(str_input):
char_arr = [i for i in str_input]
process(char_arr, 0)
def process(char_arr, i):
arr_len = len(char_arr)
if i == arr_len:
print(''.join(char_arr))
for j in range(i, arr_len):
char_arr[i], char_arr[j] = char_arr[j], char_arr[i]
process(char_arr, i + 1)
|
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| func printPermutations(input string) {
charArr := []byte(input)
process(charArr, 0)
}
func process(charArr []byte, i int) {
arrLen := len(charArr)
if i == arrLen {
fmt.Println(string(charArr))
}
for j := i; j < arrLen; j++ {
charArr[i], charArr[j] = charArr[j], charArr[i]
process(charArr, i+1)
}
}
|