String Permutation II 10
Question:
Given a string, find all permutations of it without duplicates.
Example
Given "abb", return ["abb", "bab", "bba"].
Given "aabb", return ["aabb", "abab", "baba", "bbaa", "abba", "baab"].
Solution:
与Permutation II 16解法一样。
代码如下:
public class Solution {
/**
* @param str a string
* @return all permutations
*/
public List<String> stringPermutation2(String str) {
// Write your code here
char[] string = str.toCharArray();
boolean[] isUsed = new boolean[string.length];
Arrays.sort(string);
List<String> result = new ArrayList<String>();
String temp = new String();
stringPermutation2Helper(result, temp, string, isUsed);
return result;
}
private void stringPermutation2Helper(List<String> result,
String temp,
char[] string,
boolean[] isUsed) {
if (temp.length() == string.length) {
result.add(temp);
return;
}
for (int i = 0; i < string.length; i++) {
if (isUsed[i] == true || i != 0 &&
isUsed[i - 1] == false &&
string[i] == string[i - 1]) {
continue;
}
isUsed[i] = true;
stringPermutation2Helper(result, temp + string[i], string, isUsed);
isUsed[i] = false;
}
}
}
Revised Version:
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<String>();
char[] s = str.toCharArray();
Arrays.sort(s);
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;
}
}
}