FilesExpand file tree

 master

/

Solution38.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

51 lines (44 loc) · 1.56 KB

 master

/

Solution38.java

Copy path

Top

File metadata and controls

• Code
• Blame

51 lines (44 loc) · 1.56 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

48

49

50

51

package com.usher.algorithm.offer;

import java.util.ArrayList;

import java.util.Collections;

/**

* 字符串全排列

* 1、所有可能出现在第一个位置的字符，把第一个字符和后面所有的字符交换

* 2、固定第一个字符，求后面所有字符的排列，

* 把后面所有字符再分成两部分：

* 后面字符的第一个字符，以及之后的所有字符，重复步骤1

*

* @author usher

*

*/

public class Solution38 {

public ArrayList<String> Permutation(String str) {

ArrayList<String> reStrings = new ArrayList<>();

if (str != null && str.length() > 0) {

PermutationHelper(str.toCharArray(), 0, reStrings);

Collections.sort(reStrings);

}

return reStrings;

}

private static void PermutationHelper(char[] charArray, int i, ArrayList<String> reStrings) {

// i号位置作为交换点，向后交换

// 递归出口：只剩一个字符，即无法交换

if (charArray.length - 1 == i) {

reStrings.add(String.valueOf(charArray));

} else {

for (int j = i; j < charArray.length; ++j) {

// 依次交换i与它后边的每一个字符

if (j == i || charArray[j] != charArray[i]) {// 去重复值，除了i位置与自己交换的情况

swap(charArray, i, j);

PermutationHelper(charArray, i + 1, reStrings);// 对后面所有的字符进行全排列

swap(charArray, i, j);// 再将之前交换的字符交换回来，以便第一个字符再与其他字符交换

}

}

}

}

private static void swap(char[] cs, int i, int j) {

char temp = cs[i];

cs[i] = cs[j];

cs[j] = temp;

}

}