FilesExpand file tree

 master

/

offer38.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

47 lines (44 loc) · 1.47 KB

 master

/

offer38.java

Copy path

Top

File metadata and controls

• Code
• Blame

47 lines (44 loc) · 1.47 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

import java.util.ArrayList;

import java.util.HashSet;

import java.util.List;

/**

* [38] 字符串的排列

*

* 题目: 返回给定字符串中字符的所有排列. 可以以任意顺序返回这个字符串数组, 但里面不能有重复元素.

*

* 思路: 减而治之(回溯算法): 先在给定序列中选择一个数字放在当前位置, 再对剩余的数字进行全排列, 即 f(n) = 1 + f(n - 1).

*/

class Solution {

/**

* 时间复杂度: O(A _n ^n)

* 空间复杂度: O(n)

*/

public String[] permutation(String s) {

char[] chrs = s.toCharArray();

List<String> ret = new ArrayList<>();

process(chrs, ret, 0);

return ret.toArray(new String[ret.size()]);

}

private void process(char[] chrs, List<String> ret, int index) {

if (index == chrs.length) {

ret.add(new String(chrs));

}

// use set to judge is current char used or not.

HashSet<Character> set = new HashSet<>();

for (int i = index; i < chrs.length; i++) {

if (set.contains(chrs[i])) {

continue;

}

set.add(chrs[i]);

swap(chrs, index, i);

process(chrs, ret, index + 1);

// backtrack: recover char array after recursion(very important).

swap(chrs, index, i);

}

}

private void swap(char[] chrs, int a, int b) {

char temp = chrs[b];

chrs[b] = chrs[a];

chrs[a] = temp;

}

}