原文链接: https://leetcode-cn.com/problems/permutation-ii-lcci

英文原文

Write a method to compute all permutations of a string whose characters are not necessarily unique. The list of permutations should not have duplicates.

Example1:

 Input: S = "qqe"
 Output: ["eqq","qeq","qqe"]

Example2:

 Input: S = "ab"
 Output: ["ab", "ba"]

Note:

1. All characters are English letters.
2. 1 <= S.length <= 9

中文题目

有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。

示例1:

 输入：S = "qqe"
 输出：["eqq","qeq","qqe"]

示例2:

 输入：S = "ab"
 输出：["ab", "ba"]

提示:

1. 字符都是英文字母。
2. 字符串长度在[1, 9]之间。

通过代码

高赞题解

咱不提前排序，因为我自己如果没看题解很难想到要将目标串排序。

1. 确定每次递归时可选择的数据。其实难点就在此处，最好的方法还是通过画出选择树
2. 通过下图的选择树，可以看出，当同一层选择的元素在之前选择过时，那么这个分支就是重复的，这个分支需要剪掉。

比如下图 第二层 a v a 中 第二个a就和第一a个重复，第二个a这整个分支在第一个a的分支中已经包含到了 ，所以跳过该分支即可

/**
 *                                              java
 *                j                               a                      v                     a
 *        a       v        a                  j   v   a              j   a   a             j   a   v
 *      v   a   a   a    a   v
 *      a   v   a   a    v   a
 *  java\jaav\jvaa\jvaa\jaav\java
 * /

List<String> list = new ArrayList<>();
   public String[] permutation(String S) {

       char[] chars = S.toCharArray();
       int[] used = new int[chars.length];
       StringBuilder sb = new StringBuilder();
       dfs(used,chars,sb);
       // 格式处理
       String[] res = new String[list.size()];
       for (int i = 0; i < list.size(); i++) {
           res[i] = list.get(i);
       }
       return res;
   }

   public void dfs(int[] used , char[] chars, StringBuilder sb){
       if (sb.length() == chars.length){
           list.add(sb.toString());
           return;
       }
       /**
        *                                              java
        *                j                                     a                      v                     a
        *        a       v        a                        j   v   a              j   a   a             j   a   v
        *      v   a   a   a    a   v
        *      a   v   a   a    v   a
        *  java\jaav\jvaa\jvaa\jaav\java
        *
        *  通过一个选择树可以发现问题。当有重复字母时,出现了重复的树
        *  这里通过一个技巧，这个技巧就是先排序后再处理，不过如果不看题解，我很难想到要先排序。
        *
        *  如果不先排序，那么在同一层遇到相同的字母时应该跳过，这个代码应该怎么写呢？
        *
        *
        *
        */
       /// 每次面临的选择
       for (int i = 0; i < chars.length; i++) {
           if (used[i] == 1) continue;
           /**
            *  used[j] == 0 且 chars[j] == cur 说明在同一层 此时遇到相等的元素需要剪枝，因为该分支和之前的分支重复了
            *  used[j] == 1 且 chars[j] == cur 不是同一层 此时即便遇到相等的元素也是不能剪枝的 比如第二层的a 和 第三层的a
            */
           char cur = chars[i];
           boolean valid = true;
           for (int j = 0; j < i; j++) {
               if (used[j] == 0 && chars[j] == cur){
                   /// 这个cur不能要
                   valid = false;
               }
           }
           if (!valid) continue;
           sb.append(chars[i]);
           used[i] = 1;
           dfs(used, chars, sb);
           sb.deleteCharAt(sb.length()-1);
           used[i] = 0;
       }
   }

统计信息

通过次数	提交次数	AC比率
17300	24076	71.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言