描述
给出一个字符串，找到它的所有排列，注意同一个字符串不要打印两次
样例
给出 "abb"，返回 ["abb", "bab", "bba"]。
给出 "aabb"，返回 ["aabb", "abab", "baba", "bbaa", "abba", "baab"]
代码
- DFS
public class Solution {
/*
* @param str: A string
* @return: all permutations
*/
public List<String> stringPermutation2(String str) {
// write your code here
List<String> result = new ArrayList<>();
if (str == null || str.length() == 0) {
result.add("");
return result;
}
//Sort Array beforehand for ordering purpose
str = sortString(str);
Set<String> set = new HashSet<>();
boolean[] isUsed = new boolean[str.length()];
String testStr = "";
// DFS
DFS(str, testStr, isUsed, set, result);
return result;
}
private void DFS(String str,
String testStr,
boolean[] isUsed,
Set<String> set,
List<String> result) {
if (testStr.length() == str.length()) {
result.add(new String(testStr));
return;
}
for (int i = 0; i < str.length(); i++) {
if (isUsed[i] == true || i != 0 && isUsed[i - 1] == false
&& str.charAt(i) == str.charAt(i - 1)) {
continue;
}
if (set.contains(testStr + str.charAt(i))) {
continue;
}
// 字符串拼接的方法
testStr = testStr + str.charAt(i);
set.add(testStr);
isUsed[i] = true;
DFS(str, testStr, isUsed,set, result);
testStr = testStr.substring(0, testStr.length() - 1);
set.remove(testStr);
isUsed[i] = false;
}
}
private String sortString(String str) {
char[] tempArray = str.toCharArray();
Arrays.sort(tempArray);
return new String(tempArray);
}
}
- 思路同下一个排列的题，从编号为0的排列不断寻找下一个排列，直到找到最后一个排列为止，把所有排列加入result
public class Solution {
/**
* @param str a string
* @return all permutations
*/
public List<String> stringPermutation2(String str) {
List<String> result = new ArrayList<String>();
char[] s = str.toCharArray();
Arrays.sort(s);
// String.valueOf() 将括号中的值转换成字符串
result.add(String.valueOf(s));
while ((s = nextPermutation(s)) != null) {
result.add(String.valueOf(s));
}
return result;
}
// 得到下一种组合
public char[] nextPermutation(char[] nums) {
int index = -1;
for (int i = nums.length - 1; i > 0; i--) {
if (nums[i] > nums[i - 1]){
index = i - 1;
break;
}
}
// 表示当前是最后一个排列
if (index == -1) {
return null;
}
for (int i = nums.length - 1; i > index; i--) {
if (nums[i] > nums[index]) {
char temp = nums[i];
nums[i] = nums[index];
nums[index] = temp;
break;
}
}
reverse(nums, index + 1, nums.length - 1);
return nums;
}
public void reverse(char[] num, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
char temp = num[i];
num[i] = num[j];
num[j] = temp;
}
}
}
