全排列|字母 DP

全排列
问题描述
编写一个方法，确定某字符串的所有排列组合。
解法1

文章图片

上图是对字符串ABC进行全排列的示意图，其中*代表着可插入字符的位置。
由上图可知，我们可以尝试先初始化一个仅含有首字符的链表而后在*的位置插入新的字符。

private static int f(String str) { ArrayList> res = new ArrayList<>(); res.add(str.charAt(0) + ""); // 初始化 for (int i = 1; i < str.length(); i++) { ArrayList> temp = new ArrayList<>(); char ch = str.charAt(i); // 新字符 for (String string : res) { String newString = ch + string; temp.add(newString); newString = string + ch; temp.add(newString); // 插中间 for (int j = 1; j < string.length(); j++) { newString = string.substring(0, j) + ch + string.substring(j); temp.add(newString); } } res = temp; } return res.size(); }

解法2

文章图片

【全排列|字母】如图，对ABC进行全排列可以分解成以A打头的排列+以B打头的排列+以C打头的排列的子问题。因此可用递归解决。
定义递归函数的宏观语义为，对字符数组arr的第k索引位开始进行排列并将排列结果添加到ArrayList中。

public class 全排列II { public static void main(String[] args) { ArrayList> res = new 全排列II().getPermutation("ABC"); System.out.println(res.size()); System.out.println(res); } ArrayList> res = new ArrayList<>(); public ArrayList> getPermutation(String A) { char[] arr = A.toCharArray(); Arrays.sort(arr); // abc getPermutationCore(arr, 0); return res; } // 排列并且添加 private void getPermutationCore(char[] arr, int k) { if (k == arr.length) { res.add(new String(arr)); return; }for (int i = k; i < arr.length; i++) { swap(arr, i, k); getPermutationCore(arr, k + 1); swap(arr, i, k); } } static void swap(char[] arr, int i, int j) { char tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }}