Problem

Given a string, find all permutations of it without duplicates.

Have you met this question in a real interview? Yes
Example
Given "abb", return ["abb", "bab", "bba"].

Given "aabb", return ["aabb", "abab", "baba", "bbaa", "abba", "baab"].

思路(和Permutation II 一样)

• 不同点: 将string转化成char[], 然后排序
• 可以不用visited数组吗?
  • 不可以, 不同于subset II, 因为当前元素需要记录是否访问过

    public List<String> stringPermutation2(String str) {
        List<String> result = new ArrayList<>();
        if (str == null || str.length() == 0) {
            result.add("");
            return result;
        }
        char[] arr = str.toCharArray();
        Arrays.sort(arr);
        boolean[] visited = new boolean[arr.length];
        helper(arr, result, new StringBuilder(), visited);
        return result;
    }

    private void helper(char[] arr, List<String> result, StringBuilder sb, boolean[] visited) {
        for (int i = 0; i < arr.length; i++) {
            if (visited[i]) continue;

            if (i != 0 && arr[i] == arr[i - 1] && !visited[i - 1]) continue;
            int len = sb.length();
            sb.append(arr[i]);
            visited[i] = true;
            if (sb.length() == arr.length) {
                result.add(sb.toString());
            }
            helper(arr, result, sb, visited);
            visited[i] = false;
            sb.setLength(len);
        }
    }