Permutations（4Kyu） - 图1

题目

In this kata you have to create all permutations of an input string and remove duplicates, if present. This means, you have to shuffle all letters from the input in all possible orders. 在这个kata中，您必须创建一个输入字符串的所有排列，并删除重复项（如果存在）。这意味着，您必须以所有可能的顺序将输入中的所有字母洗牌。

例子

Permutations.singlePermutations(“a”) shouldBe [“a”] Permutations.singlePermutations(“ab”) shouldBe [“ab”, “ba”] Permutations.singlePermutations(“aabb”) shouldBe [“aabb”,”abab”,”abba”,”baab”,”baba”,”bbaa”]

原题链接

分析

字符串排列组合问题，采用dfs深度优先递归遍历，将当前结果存放到cur中，直到cur长度等于s,如果最终结果result中没有cur，将cur放入result中。需要注意的是加了一个flag判断当前字符是否在本次dfs中出现过，每次遍历完一个字符后需要复位既flag置为false、cur去掉当前加上的字符。

我的解法

  1. import java.util.*;
  3. class Permutations {
  5.     public static List<String> singlePermutations(String s) {
  6.         return permutation(s, new boolean[s.length()], "", new ArrayList<>());
  7.     }
  8.     public static List<String> permutation(String s, boolean[] flag, String cur, List<String> result) {
  9.         if (cur.length() == s.length() && !result.contains(cur)) {
  10.             result.add(cur);
  11.         }
  12.         for (int i = 0; i < s.length(); i++) {
  13.             if (!flag[i]) {
  14.                 flag[i] = true;
  15.                 cur += s.charAt(i);
  16.                 permutation(s, flag, cur, result);
  17.                 cur = cur.substring(0, cur.length() - 1);
  18.                 flag[i] = false;
  19.             }
  20.         }
  21.         return result;
  22.     }
  23. }

参考解法

  1. import static java.util.Collections.singletonList;
  2. import static java.util.stream.Collectors.toList;
  4. import java.util.List;
  6. class Permutations {
  8.   public static List<String> singlePermutations(final String s) {
  9.     return permute("", s);
  10.   }
  12.   private static List<String> permute(final String prefix, final String s) {
  14.     return s.isEmpty()
  15.         ? singletonList(prefix)
  16.         : s.chars()
  17.             .distinct()
  18.             .mapToObj(i -> (char) i)
  19.             .map(c -> permute(prefix + c, takeOut(s, c)))
  20.             .flatMap(List::stream)
  21.             .collect(toList());
  22.   }
  24.   static String takeOut(final String s, final char c) {
  25.     final int i = s.indexOf(c);
  26.     return s.substring(0, i) + s.substring(i + 1);
  27.   }
  28. }

动态规划的解法

  1. import java.util.*;
  3. class Permutations {
  5.     public static List<String> singlePermutations(String s) {
  7.         // Your code here!
  8.         return permutate("",s,new ArrayList<String>());
  9.     }
  10.     public static List<String> permutate(String permute, String s, List<String> listed) {
  11.       if (s.isEmpty() &&  !listed.contains(permute + s)) {
  12.         listed.add(permute + s);
  13.       } else {
  14.         for (int i = 0; i < s.length(); i++) {
  15.           permutate(permute + s.charAt(i), s.substring(0,i) + s.substring(i+1,s.length()), listed);
  16.         }
  17.       }
  18.       return listed;
  19.     }
  20. }

提升

  1. 解决排列组合中心思想是分治和递归
  2. 分治：就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
  3. dfs伪代码如下
    1. void dfs(int step)
    2. {
    3.      判断边界
    4.      {
    5.          相应操作
    6.      }
    7.      尝试每一种可能
    8.      {
    9.             满足check条件
    10.             {
    11.               标记
    12.               继续下一步dfs(step+1)
    13.               恢复初始状态（回溯的时候要用到）
    14.             }
    15.      }
    16. }

    参考资料

    回溯算法套路详解