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;
        }
    }
}